【枚举】CF1660 D

缺乏、安全感 2024-03-23 21:52 64阅读 0赞

[Problem - 1660D - Codeforces][]

题意：

![208a35e52d4f4427a5e8eabf77f136e7.png][]

思路：

思路巨简单，代码也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;
    }

[Problem - 1660D - Codeforces]: https://codeforces.com/problemset/problem/1660/D
[208a35e52d4f4427a5e8eabf77f136e7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/eb3b2593ce9e4af3a48965bb059aec68.png