【链接】
https://hihocoder.com/problemset/problem/1835
【题意】
已知 ：sigma | ai |=r
最小化：sigma ((bi-ai)^2)
求每个ai
【分析】
将中心点移动到原点。相当于：要ai-1，显然是大的那个数-1比较小。然后想象一下，最后的ai一般来说都是，几个数都是最大的数，其余数不改变。那么我们二分这个减少后的最大的数。然后求出ans
【代码】
#include<bits/stdc++.h> using namespace std; const int maxn = 1e5 + 6; const double eps = 1e-4; double a[maxn]; double o[maxn]; double c[maxn]; double ans[maxn]; int main() { int t; scanf("%d", &t); while (t--) { int n, k; double r; scanf("%d%d%lf", &n, &k, &r); for (int i = 0; i < k; i++) { scanf("%lf", &o[i]); } for (int i = 0; i < n; i++) { for (int j = 0; j < k; j++) { scanf("%lf", &a[j]); c[j] = fabs(a[j] - o[j]); } double L = 0; double R = 1e18; double mid; while (R-L>= eps) { mid = (L + R) / 2; double sum = 0; for (int j = 0; j < k; j++) { sum += max(0.0, c[j] - mid); } if (sum > r) { L = mid; } else { R = mid; } } for (int j = 0; j < k; j++) { if (c[j] >= R)c[j] = R; if (a[j] > o[j])ans[j] = -c[j] + a[j]; else ans[j] = c[j] + a[j]; printf("%.5f ", ans[j]); } printf("\n"); } } }
