题解 P2672 【推销员】
Creeper_LKF
2018-07-20 16:02:38
# 结构体基排
$\ \ \ \ $这个题目本身其实并不难，我这里为了减小常数用的思想是贪心：
> $\ \ \ \ $注意到$a$对于答案的贡献是$\Sigma{a}$，但是$s$对答案的贡献是$2 * Max\{s\}$
> $\ \ \ \ $分析对于推销$k$个人答案的组成：要么答案就是由$a$值最大的$k$个人构成，要么答案是由$a$值最大的$k-1$个人和一个$s$非常大的人构成
$\ \ \ \ $然后我就~~沉迷于卡常~~无法自拔了
$\ \ \ \ $按照这个算法的标准代码应该是这样：
``` cpp
#include <cstdio>
#include <fcntl.h>
#include <unistd.h>
#include <sys/mman.h>
//User's Lib
#include <algorithm>
using namespace std;
char *pc;
inline void Main_Init(){
static bool inited = false;
if(inited) fclose(stdin), fclose(stdout);
else {
#ifndef ONLINE_JUDGE
freopen("b.in", "r", stdin);
freopen("b.out", "w", stdout);
#endif
pc = (char *) mmap(NULL, lseek(0, 0, SEEK_END), PROT_READ, MAP_PRIVATE, 0, 0);
inited = true;
}
}
inline int read(){
int num = 0;
char c;
while((c = *pc ++) < 48);
while(num = num * 10 + c - 48, (c = *pc ++) >= 48);
return num;
}
namespace LKF{
template <typename T>
extern inline T abs(T tar){
return tar < 0 ? -tar : tar;
}
template <typename T>
extern inline void swap(T &a, T &b){
T t = a;
a = b;
b = t;
}
template <typename T>
extern inline void upmax(T &x, const T &y){
if(x < y) x = y;
}
template <typename T>
extern inline void upmin(T &x, const T &y){
if(x > y) x = y;
}
template <typename T>
extern inline T max(T a, T b){
return a > b ? a : b;
}
template <typename T>
extern inline T min(T a, T b){
return a < b ? a : b;
}
}
//Do not copy from other files
//Source Code
const int MAXN = 100011;
struct Data{
int a, s;
inline bool operator < (const Data &tar) const {
return a > tar.a;
}
}data[MAXN];
int val[MAXN];
int main(){
Main_Init();
int n = read();
for(register int i = 1; i <= n; i++)
data[i].s = read();
for(register int i = 1; i <= n; i++)
data[i].a = read();
stable_sort(data + 1, data + 1 + n);
for(register int i = n; i >= 1; i--){
val[i] = LKF::max(val[i + 1], (data[i].s << 1) + data[i].a);
__builtin_prefetch(val + i - 1, 1, 0);
}
int Sum1 = 0, Sum2 = 0, Max = 0;
for(register int i = 1; i <= n; i++){
Sum1 += data[i].a;
LKF::upmax(Max, data[i].s);
printf("%d\n", LKF::max(Sum1 + (Max << 1), Sum2 + val[i]));
Sum2 += data[i].a;
__builtin_prefetch(data + i + 1, 0, 0);
}
Main_Init();
return 0;
}
```
$\ \ \ \ $我们注意到需要一次以$a$为关键字排序，但是考虑到单关键字排序，我们是否可以使用基数排序呢？
$\ \ \ \ $于是就尝试把结构体首先以指针方法取成int（为了取$a$作为关键字），然后按照正常方法进行基数排序，然后就成功了，只是常数稍大
$\ \ \ \ $代码如下：
``` cpp
#include <cstdio>
#include <fcntl.h>
#include <unistd.h>
#include <sys/mman.h>
//User's Lib
#include <cstring>
// #include <algorithm>
using namespace std;
char *pc;
char outp[1111111], *op = outp;
inline void Main_Init(){
static bool inited = false;
if(inited){
fwrite(outp, 1, op - outp - 1, stdout);
fclose(stdin), fclose(stdout);
} else {
#ifndef ONLINE_JUDGE
freopen("b.in", "r", stdin);
#endif
pc = (char *) mmap(NULL, lseek(0, 0, SEEK_END), PROT_READ, MAP_PRIVATE, 0, 0);
inited = true;
}
}
inline int read(){
int num = 0;
char c;
while((c = *pc ++) < 48);
while(num = num * 10 + c - 48, (c = *pc ++) >= 48);
return num;
}
inline void Write(const int &tar){
if(!tar) return ;
Write(tar / 10);
*op ++ = (tar % 10) ^ 48;
}
namespace LKF{
template <typename T>
extern inline T abs(T tar){
return tar < 0 ? -tar : tar;
}
template <typename T>
extern inline void swap(T &a, T &b){
T t = a;
a = b;
b = t;
}
template <typename T>
extern inline void upmax(T &x, const T &y){
if(x < y) x = y;
}
template <typename T>
extern inline void upmin(T &x, const T &y){
if(x > y) x = y;
}
template <typename T>
extern inline T max(T a, T b){
return a > b ? a : b;
}
template <typename T>
extern inline T min(T a, T b){
return a < b ? a : b;
}
}
//Do not copy from other files
//Source Code
const int MAXN = 100011;
struct Data{
int a, s;
}data[MAXN], tmp_data[MAXN];
template <typename T>
inline void Radix_Sort(register const int n, T *a, T *b){
int r1[0xff], r2[0xff], r3[0xff], r4[0xff];
memset(r1, 0, sizeof(r1)), memset(r2, 0, sizeof(r2));
memset(r3, 0, sizeof(r3)), memset(r4, 0, sizeof(r4));
register int i, tmp_int;
register T * j, *tar;
for(j = a + 1, tar = a + 1 + n; j != tar; ++j){
tmp_int = * (int *) j;
++r1[tmp_int & 0xff];
++r2[(tmp_int >> 8) & 0xff];
++r3[(tmp_int >> 16) & 0xff];
++r4[tmp_int >> 24];
}
for(i = 1; i <= 0xff; ++i){
r1[i] += r1[i - 1];
r2[i] += r2[i - 1];
r3[i] += r3[i - 1];
r4[i] += r4[i - 1];
}
for(j = a + n; j != a; --j){
tmp_int = * (int *) j;
b[r1[tmp_int & 0xff]--] = *j;
}
for(j = b + n; j != b; --j){
tmp_int = * (int *) j;
a[r2[(tmp_int >> 8) & 0xff]--] = *j;
}
for(j = a + n; j != a; --j){
tmp_int = * (int *) j;
b[r3[(tmp_int >> 16) & 0xff]--] = *j;
}
for(j = b + n; j != b; --j){
tmp_int = * (int *) j;
a[r4[tmp_int >> 24]--] = *j;
}
}
int val[MAXN];
int main(){
Main_Init();
int n = read();
for(register int i = 1; i <= n; ++ i)
data[i].s = read();
for(register int i = 1; i <= n; ++ i)
data[i].a = read();
Radix_Sort(n, data, tmp_data);
for(register int i = 1, j = n; i < j; ++ i, -- j)
LKF::swap(data[i], data[j]);
// stable_sort(data + 1, data + 1 + n);
for(register int i = n; i >= 1; i--){
val[i] = LKF::max(val[i + 1], (data[i].s << 1) + data[i].a);
__builtin_prefetch(val + i - 1, 1, 0);
}
int Sum1 = 0, Sum2 = 0, Max = 0;
for(register int i = 1; i <= n; ++ i){
Sum1 += data[i].a;
LKF::upmax(Max, data[i].s);
Write(LKF::max(Sum1 + (Max << 1), Sum2 + val[i])), *op ++ = '\n';
Sum2 += data[i].a;
__builtin_prefetch(data + i + 1, 0, 0);
}
Main_Init();
return 0;
}
```