题解 P2672 【推销员】

2018-07-20 16:02:38


结构体基排

$\ \ \ \ $这个题目本身其实并不难,我这里为了减小常数用的思想是贪心:

$\ \ \ \ $注意到$a$对于答案的贡献是$\Sigma{a}$,但是$s$对答案的贡献是$2 * Max\{s\}$
$\ \ \ \ $分析对于推销$k$个人答案的组成:要么答案就是由$a$值最大的$k$个人构成,要么答案是由$a$值最大的$k-1$个人和一个$s$非常大的人构成

$\ \ \ \ $然后我就沉迷于卡常无法自拔了
$\ \ \ \ $按照这个算法的标准代码应该是这样:

#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$作为关键字),然后按照正常方法进行基数排序,然后就成功了,只是常数稍大
$\ \ \ \ $代码如下:

#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;
}