Description
有n件商品，选出其中的k个，要求它们的总价为奇数，求最大可能的总价。
第一行一个整数n(1<=n<=1000000)，表示商品数量。
接下来一行有n个整数，表示每件商品的价格，范围在[1,10^9]。
接下来一行有一个整数m(1<=m<=1000000)，表示询问数量。
接下来m行，每行一个整数ki。
Output
对于每个询问，输出一行表示保证奇数的情况下最大的总价。若无法满足要求，输出-1。
4
4 2 1 3
3
2
3
4
Sample Output
7
9
-1
Solution
贪心。
先排序。对于每个k，看看能选前k个就选，不能选就分情况讨论（删掉前面的奇数或偶数，加上后面奇数或偶数，删掉这个数加上后面奇数或偶数）
还有这题需要注意IO优化，不优化会T得很惨QAQ。。。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
| #include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int INF = 1009999999;
int getint() {
int r = 0, k = 1; char c = getchar();
for (; '0' > c || c > '9'; c = getchar()) if (c == '-') k = -1;
for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
return r * k;
}
char dst[128]; int ptr;
void putll(LL x) {
do {
dst[++ptr] = x % 10;
x /= 10;
} while (x);
while (ptr)
putchar(dst[ptr--]+'0');
putchar('\n');
}
int n, m;
const int maxn = 1000005;
LL E[maxn];
int nxt1[maxn], nxt0[maxn], lst1[maxn], lst0[maxn], C[maxn], A[maxn];
bool cmp(int a, int b) { return a > b; }
int main() {
n = getint();
for (int i = 1; i <= n; ++i)
A[i] = getint();
sort(A+1, A+1+n, cmp);
int tmp0 = 0, tmp1 = 0;
for (int i = 1; i <= n; ++i) {
C[i] = (A[i] & 1) ^ C[i-1];
E[i] = E[i-1] + A[i];
lst0[i] = tmp0;
lst1[i] = tmp1;
if (A[i] & 1) tmp1 = i;
else tmp0 = i;
}
tmp0 = 0, tmp1 = 0;
for (int i = n; i; --i) {
nxt0[i] = tmp0;
nxt1[i] = tmp1;
if (A[i] & 1) tmp1 = i;
else tmp0 = i;
}
m = getint();
int k;
while (m--) {
k = getint();
if (C[k]) putll(E[k]);
else {
LL ans = -1;
if (nxt0[k]) {
if (lst1[k]) ans = max(ans, E[k] - A[lst1[k]] + A[nxt0[k]]);
if ((A[k] & 1)) ans = max(ans, E[k] - A[k] + A[nxt0[k]]);
}
if (nxt1[k]) {
if (lst0[k]) ans = max(ans, E[k] - A[lst0[k]] + A[nxt1[k]]);
if (!(A[k] & 1)) ans = max(ans, E[k] - A[k] + A[nxt1[k]]);
}
if (ans == -1) {
putchar('-');
putchar('1');
putchar('\n');
}
else putll(ans);
}
}
return 0;
}
|