题解：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

执行减一结果相同相同。

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

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

总时间复杂度：

\mathcal{O}(n(k_1+k_2))

，可以通过（

n, k_1 + k_2\le 10^3

）。

代码实现

要开 long long！

CPP

#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;
}

题解：CF960B Minimize the error

文章操作

题意

做法分析

代码实现

相关推荐

评论

题解：CF960B Minimize the error