Problem - 1660D - Codeforces

题意：

思路：

思路巨简单，代码也wa了很多发才过，都是因为细节....

很显然，要根据0分段处理

对于每一段，枚举去掉左边段还是右边段，左边段是 l 到第一个负数，右边段是最后一个负数到 r，看哪个大

比较的话不需要把区间积算出来，比较区间2的个数即可

如果区间积本来就是正数，那么直接取一整段即可

Code：

#include <bits/stdc++.h>using i64 = long long;constexpr int N = 2e5 + 10;
constexpr int M = 2e5 + 10;std::vector<std::array<int, 2> > V;int pl = 1, pr = 1;
int a[N], pre[N], pre2[N];int calc(int l, int r) {if(l == r && a[l] < 0) return -1e9;int cnt = pre[r] - pre[l - 1];if (cnt & 1) {int mx = 0, L = 0, R = 0;for (int i = l; i <= r; i ++) {if (a[i] < 0) {L = i;break;}}for (int i = r; i >= l; i --) {if (a[i] < 0) {R = i;break;}}if (pre2[r] - pre2[L + 1 - 1] > pre2[R - 1] - pre2[l - 1]) {pl = L + 1;pr = r;}else {pl = l;pr = R - 1;}mx = std::max(pre2[r] - pre2[L + 1 - 1], pre2[R - 1] - pre2[l - 1]);return mx;}else {pl = l, pr = r;return pre2[r] - pre2[l - 1];}
}
void solve() {V.clear();pl = 0, pr = 0;int n;std::cin >> n;for (int i = 0; i <= n + 5; i ++) {a[i] = pre[i] = pre2[i] = 0;}for (int i = 1; i <= n; i ++) {std::cin >> a[i];}if (n == 1) {if (a[1] > 0) {std::cout << "0 0" << "\n";}else {std::cout << "1 0" << "\n";}return;}for (int i = 1; i <= n; i ++) {pre[i] = pre[i - 1] + (a[i] < 0);pre2[i] = pre2[i - 1] + (abs(a[i]) == 2);}a[n + 1] = 0;int l = 1, r = 1;for (int i = 1; i <= n + 1; i ++) {if (a[i] == 0) {r = i - 1;if (l <= r) V.push_back({l, r});l = i + 1;}}int ans = -1e9, ansl = 0, ansr = 0;for (auto v : V) {if (ans < calc(v[0], v[1])) {ans = calc(v[0], v[1]);ansl = pl;ansr = pr;}}if (ansl == 0 && ansr == 0) std::cout << n << " " << 0 << "\n";else std::cout << ansl - 1 << " " << n - (ansr + 1) + 1 << "\n";
}
signed main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t = 1;std::cin >> t;while(t --) {solve();}return 0;
}