B. Odd sum - Educational Codeforces Round 19
Solutions Codeforces 贪心 1400 Easy-
Lastmod: 2025-01-06 周一 20:50:18

https://codeforces.com/contest/797/problem/B

题目大意

给出长度 $n \ (\le 10^5)$ 长的数组 $a \ (-10^4 \le a_i \le 10^4)$,保证其有和为奇数的子序列,问和为奇数的子序列最大是多少。

简要题解

显然我们要尽量选所有的正数让和尽量大,但这时如果和是偶数,那我们就需要减掉最小的正奇数或者加上最大的负奇数得到一个奇数和。注意这里有两种情况。(感觉完全不值 1400 分)

复杂度

$T$:$O(n)$

$S$:$O(n)$

代码实现

#include <bits/stdc++.h>
using namespace std;

int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();

using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;

template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) { 
    return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) { 
    return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z 
    if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
    if(x<z) { y=x; x=z; } else if(y<z) y=z; }

// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());

/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/

const int INF = 0x3f3f3f3f;

void solve() {
  int n; cin >> n;
  vector<int> a(n);
  for (int& i : a) cin >> i;

  int sum = 0;
  int mnp = INF, mxn = -INF;
  for (int i : a) {
    if (i > 0) {
      sum += i;
      if (i & 1) {
        cmin(mnp, i);
      }
    } else if (i < 0) {
      if (i & 1) {
        cmax(mxn, i);
      }
    }
  }

  if (sum & 1) {
    cout << sum << '\n';
  } else {
    int ans = -INF;
    if (mnp < INF) cmax(ans, sum - mnp);
    if (mxn > -INF) cmax(ans, sum + mxn);
    cout << ans << '\n';
  }
}

int main() {
  int t = 1; 
  // cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}
Prev: B. Counting-out Rhyme - Educational Codeforces Round 18
Next: C. Minimal string - Educational Codeforces Round 19