题解归档 - cf2222B

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2222B
• 本地来源：problems/cf2222B/idea.md
• 题目链接：https://codeforces.com/contest/2222/problem/B
• 原始标题：cf2222B - Artistic Balance Tree

思路

cf2222B - Artistic Balance Tree

Pattern

The allowed operation reverses an odd-length segment around its center. Each
swapped pair has the same index parity, so an element never changes parity.

Inside one parity class, these reversals are ordinary contiguous reversals, and
they generate any permutation of that parity class. Thus, before an operation
whose marked index has parity p, we may choose any element of parity p to be
there.

If a parity appears in the operation list, the first such operation must mark
one element of that parity. Later operations may either mark a new element or
place an already marked element there to avoid marking a bad value.

Algorithm

For each parity independently:

• let c be the number of operations on this parity;
• if c=0, mark nothing;
• otherwise sort values of this parity descending and choose the prefix length
  k with 1 <= k <= c that maximizes the prefix sum.

The answer is total sum minus the maximum marked sum over both parity classes.

Checks

• python tools/math_reasoning_search.py --problem cf2222B -n 5 - required
  precheck done.

代码

来源：problems/cf2222B/solution.cpp

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

using ll = long long;

static ll best_marked_sum(vector<ll> values, int operations) {
    if (operations == 0) return 0;
    sort(values.begin(), values.end(), greater<ll>());
    int take_limit = min<int>(operations, values.size());
    ll best = values[0];
    ll cur = 0;
    for (int i = 0; i < take_limit; i++) {
        cur += values[i];
        best = max(best, cur);
    }
    return best;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        vector<ll> odd, even;
        ll total = 0;
        for (int i = 1; i <= n; i++) {
            ll x;
            cin >> x;
            total += x;
            if (i & 1) odd.push_back(x);
            else even.push_back(x);
        }
        int odd_ops = 0, even_ops = 0;
        for (int i = 0; i < m; i++) {
            int x;
            cin >> x;
            if (x & 1) odd_ops++;
            else even_ops++;
        }

        ll marked = best_marked_sum(odd, odd_ops) + best_marked_sum(even, even_ops);
        cout << total - marked << '\n';
    }
    return 0;
}