题目传送门(BZOJ)

题解 :

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

代码 :

#include <queue>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;#define ll long longconst 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 maxinumint 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原创, 转载必须以链接形式注明>原文链接<