题解：CF1832D1 Red-Blue Operations (Easy Version)

ka_da_Duck · 2024-07-30 16:14:46 · 题解

分情况讨论。

• 我们容易想到给一个位置不断地更新，但是这样明显不是最优解，那么，我们可以利用题目所给的每一个的初始红色。 先把数组从小到大进行排序，再从前往后依次给 $a_i$ 加上 $k,k-1\ldots 2,1$，最后扫一遍求出最大值，时间复杂度 $O(n\log n)$。
• 先消耗 $n$ 次操作，对其按照 $k\le n$ 的做法更新，此时所有位置都是蓝色的。 我们对每个数做偶数次操作，每两次操作 $+1$，最后可能剩下一个操作（减），我们把它丢给最大的，再计算最大值。

代码：

#include <bits/stdc++.h>
#define int long long

using namespace std;
const int maxn = 1e4 + 10;

int n, q;
int a[maxn];

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    sort(a + 1, a + n + 1);
    while (q--) {
        int s = 0, x, ans = 1e18;
        cin >> x;
        for (int i = 1; i <= n; ++i) {
            if (!x) {
                ans = min(ans, a[i]);
                continue;
            }
            if (i == n) {
                if (x & 1) {
                    s += a[i] + x;
                    ans = min(a[i] + x, ans);
                    x--;
                    s -= x / 2;
                    ans = min(ans, s / n);
                } else {
                    s += a[i] - x / 2;
                    ans = min({ans, a[i], s / n});
                }
            } else ans = min(ans, a[i] + x), s += a[i] + x;
            if (x != 0) x--;
        }
        cout << ans << ' ';
    }
}