CF2148D 题解

RyanLi · 2025-09-22 16:37:52 · 题解

传送门：洛谷 CF2148D Destruction of the Dandelion Fields | Codeforces D. Destruction of the Dandelion Fields

更佳的阅读体验：CF2148D 题解

简要题意：有 n 块田地，每块田地有 a_i 朵蒲公英。若访问的田地的 a_i 为奇数，割草机会切换开关状态。如果割草机是开着的，就会割掉这块田地的所有蒲公英。可以任意排列访问顺序，问最多能割掉多少朵蒲公英。

首先可以确定的是，只要有 a_i 为奇数的田地，那么第一个访问奇数的田地，之后一次性访问所有偶数的田地，那么所有 a_i 为偶数的田地是一定可以被割掉的。

接下来考虑如何安排 a_i 为奇数的田地的顺序。为了使得总和尽可能大，我们考虑一种类似「大、小、大、小、……」的安排方案。这样，访问到 a_i 较大的田地时，割草机总是开的。

记奇数个数为 n。如果奇数个数非零，答案就是所有偶数的和加上最大的 \left \lceil \dfrac{n}{2} \right \rceil 个奇数的和；否则答案为 0。

#include <iostream>
#include <algorithm>
using namespace std;
using ll = long long;

const int N = 2e5 + 10;
int t, n;
ll a, ans;
basic_string<ll> odd, even;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    for (cin >> t; t; --t) {
        ans = 0;
        odd.clear(), even.clear();
        cin >> n;
        for (int i = 1; i <= n; ++i) {
            cin >> a;
            if (a & 1) odd += a;
            else even += a;
        } if (!odd.size()) {
            cout << "0\n";
            continue;
        } for (auto p : even) ans += p;
        sort(odd.begin(), odd.end(), greater<>());
        for (int i = 0; i < (odd.size() + 1) / 2; ++i) ans += odd[i];
        cout << ans << '\n';
    } return 0;
}