ZJYYCOJ-最大奇数和

题目链接: http://acm.oinsm.com/problem.php?cid=1031&pid=10

在这里插入图片描述

思路

可模拟可贪心

  1. 首先,我们能想到,既然要和为奇数,那么必然是奇数个奇数相加,偶数随意!(QAQ… 这点比赛考虑到位了!
  2. 其次必然要剪枝一下,或者再贪一下,(这个,比赛的时候我没考虑到位,超时n发,原因是我做了重复的相加操作,这里我没用前缀和优化一下即可
  3. 然后我们可以再贪一下,标记下,偶数哪一段从哪里开始就变负数了,对于负数我们可以直接抛弃掉!(当然奇数也可以这样贪一下,但是可能还得考虑再仔细一点!
  4. 到此为止,贪的也差不多了,优化的也差不多了!刚好够AC(hahahaha
  5. 对了还有最后一点,这题写了最多可以取k个,不是就取k个,这个我到比赛结束都没发现这个问题(QAQ…

    代码

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
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const long long INF = 1e16 + 7;
bool cmp(long long a, long long b) {
return a > b;
}
typedef long long ll;
ll anum[MAXN], bnum[MAXN];
int main()
{
ios::sync_with_stdio(false);
int n, m;
while(cin >> n >> m) {
int aa = 0, bb = 0;
for(int i = 1; i <= n; i++){
ll k;
cin >> k;
if(k % 2) anum[aa++] = k;
else bnum[bb++] = k;
}
sort(anum, anum + aa, cmp);
sort(bnum, bnum + bb, cmp);
int tmpa = aa, tmpb = bb;
// 求一下前缀和
for(int i = 1; i < aa; i++) {
anum[i] += anum[i - 1];
}
// 这里我们贪一下,出现负数的直接丢了
for(int i = 1; i < bb; i++) {
if(bnum[i] < 0) {
tmpb = i;
break;
}
bnum[i] += bnum[i - 1];
}
// 如果第一个偶数就为负数,那么偶数就没必要加了
if(bnum[0] < 0) tmpb = 0;
long long ans = anum[0];
for(int i = 1; i <= m && i <= tmpa; i += 2) {
ll tmp = -1;
if((m - i) >= tmpb) {
if(tmpb != 0) {
tmp = anum[i - 1] + bnum[tmpb - 1];
}
else {
tmp = anum[i - 1];
}
}
else {
tmp = anum[i - 1] + bnum[m - i - 1];
}
ans = max(ans, tmp);
}
cout << ans << endl;
}
return 0;
}

本文标题:ZJYYCOJ-最大奇数和

文章作者:HKer_YM

发布时间:2020年03月16日 - 12:14:38

最后更新:2020年03月16日 - 12:16:15

原始链接:https://blog.dreams-wj.top/2020/03/16/ZJYYCOJ-%E6%9C%80%E5%A4%A7%E5%A5%87%E6%95%B0%E5%92%8C/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。