JZOJ 6899. 【2020.11.27提高组模拟】第三题
题解
-
题意可以转化为给定一个序列 a a a，求一个由非负数构成的序列 b b b，使得 ∑ b i = C sum b_i=C ∑bi=C且 ∑ ( a i − b i ) 2 sum (a_i-b_i)^2 ∑(ai−bi)2最小。
-
由均值不等式或尝试得出，当所有 a i − b i a_i-b_i ai−bi都相等时，可以使得 ∑ ( a i − b i ) 2 sum (a_i-b_i)^2 ∑(ai−bi)2最小，但是这样并不能保证每个 b i b_i bi都是正数，把 a i a_i ai按升序排好后，前面可能会有一段对应的 b i b_i bi全都为 0 0 0，而后面的都满足 a i − b i a_i-b_i ai−bi都相等。
-
那么这段 0 0 0的长度怎么求得？
-
直接枚举 0 0 0的长度有多长，每种合法的情况取最小值即可。
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 100010
#define ll long long
#define ld long double
ll f[N], g[N], s[N][2];
struct num {
ll x; int id;
}a[N];
ll gcd(ll x, ll y) {
return y ? gcd(y, x % y) : x;
}
int cmp(num x, num y) {
return x.x < y.x;
}
int main() {
int n, C, i;
scanf("%d%d", &n, &C);
for(i = 1; i <= n; i++) scanf("%lld", &a[i].x), a[i].id = i;
sort(a + 1, a + n + 1, cmp);
f[0] = 0;
for(i = 1; i <= n; i++) f[i] = f[i - 1] + a[i].x * a[i].x;
g[n + 1] = 0;
for(i = n; i; i--) g[i] = g[i + 1] + a[i].x;
ld ans = -1; int p;
for(i = 0; i < n; i++) {
ld t = (g[i + 1] - C) / (ld)(n - i);
if((ld)a[i + 1].x - t >= 0 && (ans == -1 || f[i] + t * t * (n - i) < ans)) ans = f[i] + t * t * (n - i), p = i;
}
for(i = 1; i <= p; i++) s[a[i].id][0] = 0, s[a[i].id][1] = 1;
for(i = p + 1; i <= n; i++) {
s[a[i].id][0] = a[i].x * (n - p) - g[p + 1] + C, s[a[i].id][1] = n - p;
}
for(i = 1; i <= n; i++) {
if(s[i][1] == 1) printf("%d
", s[i][0]);
else {
int g = gcd(s[i][0], s[i][1]);
if(g == s[i][1]) printf("%d
", s[i][0] / g);
else printf("%d/%d
", s[i][0] / g, s[i][1] / g);
}
}
return 0;
}