题解：CF960B Minimize the error

· · 题解

题目传送门

真是一道暴力好题（

题意

你可以对序列 a 执行 k_1 次操作，对序列 b 执行 k_2 次操作，每次可以将对应序列的某个元素增加或减少 1，求 \sum_{i=1}^n(a_i - b_i)^2 的最小值。

做法分析

首先观察题目给的柿子，我们要让每对 (a_i - b_i)^2 最小。

发现：对一个序列执行一种操作与对另一个序列执行相反操作的结果相同，因为两个数更改后的差相同。

具体地，对 a_i 执行加一和对 b_i 执行减一结果相同相同，对 b_i 执行加一和对 a_i 执行减一结果相同相同。

根据平方的计算方法，发现只要让它们两个尽量接近，就能使使结果最优。

  1. 对于序列 a，执行 k_1 次操作，每次 \mathcal{O}(n) 找到相差最大的 a_i 和 b_i。如果 a_i 大于 b_i，将 a_i 减一，反之加一。
  2. 对于序列 b，执行 k_2 次操作，每次找到相差最大的 a_i 和 b_i。如果 a_i 大于 b_i，将 b_i 加一，反之减一。
  3. 最后统计结果即可。

总时间复杂度：\mathcal{O}(n(k_1+k_2))，可以通过（n, k_1 + k_2\le 10^3）。

代码实现

要开 long long！

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

const int N = 1e3 + 2, lmin = LLONG_MIN;

int _, n, k1, k2, ans, a[N], b[N], c[N];

signed main() {
    cin >> n >> k1 >> k2;
    for (int i = 1;i <= n;i++) cin >> a[i];
    for (int i = 1;i <= n;i++) cin >> b[i];
    for (int i = 1;i <= k1;i++) {
        int maxn = lmin, maxi;
        for (int i = 1;i <= n;i++) if (abs(a[i] - b[i]) > maxn) maxn = abs(a[i] - b[i]), maxi = i;
        if (a[maxi] > b[maxi]) a[maxi]--;
        else a[maxi]++;
    }
    for (int i = 1;i <= k2;i++) {
        int maxn = lmin, maxi;
        for (int i = 1;i <= n;i++) if (abs(a[i] - b[i]) > maxn) maxn = abs(a[i] - b[i]), maxi = i;
        if (a[maxi] > b[maxi]) b[maxi]++;
        else b[maxi]--;
    }
    for (int i = 1;i <= n;i++) ans += (a[i] - b[i]) * (a[i] - b[i]);
    cout << ans << endl;
    return 0;
}