BZOJ 3721: PA2014 Bazarek – [贪心]

题目传送门(BZOJ)

题解 :

考虑对于一个询问 K 怎么做
我们先把原序列降序排好序, 先取前 K 个, 若已经是奇数了, 那么直接输出即可
否则, 有两种方案 :
– 删掉一个取得的里最小的奇数, 加上一个没取得的中最大的偶数
– 删掉一个取得的里最小的偶数, 加上一个没取得的中最大的奇数
我们可以先将最多 N 个答案都处理出来
在排序之后, 找一个取得的里最小的奇数/偶数, 就相当于在这个取完之后的前缀里找一个最小的奇数/偶数
找一个没有取得的里最大的奇数/偶数, 就相当于在删掉这个前缀的后缀里找一个最大的奇数/偶数
我们递推维护一个前缀奇偶最小值和一个后缀奇偶最大值即可
或者用 STL set 维护亦可, 但是注意常数问题, 这题维护数组就已经很卡了 (TL : 20s, Me: 7s (With fread))

代码 :

#include 
#include 
#include 
#include 
#include 
using namespace std;
#define ll long long
const int N = 1001000;
#define nc() p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2)?EOF:*p1++
char buf[100000], *p1, *p2;
inline char gc() {
    char ch = nc();
    while(isspace(ch)) ch = nc();
    return ch;
}
inline int rd() {
    int x = 0, f = 1; char ch = nc();
    while(!isdigit(ch)) ch = nc();
    while( isdigit(ch)) x = (((x<<2)+x)<<1)+(ch^48), ch = nc();
    return x*f;
}
ll pre[2][N], suf[2][N];
ll ans[N], sum;
// pre mininum suf maxinum
int a[N];
inline bool cmp(const int &A, const int &B) {
    return A > B;
}
int main() {
    int n = rd();
    for(int i = 1; i <= n; i ++ ) a[i] = rd();
    sort(a+1, a+n+1, cmp);
    pre[0][0] = pre[1][0] = 1ll << 50;
    suf[0][n+1] = suf[1][n+1] = -(1ll << 50);
    for(int i = 1; i <= n; i ++ ) {
        pre[a[i]&1][i] = a[i],
        pre[!(a[i]&1)][i] = pre[!(a[i]&1)][i-1];
    }
    for(int i = n; i >= 1; i -- ) {
        suf[a[i]&1][i] = a[i],
        suf[!(a[i]&1)][i] = suf[!(a[i]&1)][i+1];
    }
    for(int i = 1; i <= n; i ++ ) {
        sum += a[i];
        if(sum & 1) ans[i] = sum;
        else {
            ans[i] = -1;
            ans[i] = max(ans[i], sum-pre[0][i]+suf[1][i+1]);
            ans[i] = max(ans[i], sum-pre[1][i]+suf[0][i+1]);
        }
    }
    int m = rd();
    while(m -- ) {
        printf("%lld\n", ans[rd()]);
    }
    return 0;
}

本文为Yirannn原创, 转载必须以链接形式注明>原文链接<