【2018icpc北京网络赛】【数学】【贪心】【思维】【条件极值】

xiaoxiao2021-03-01  11

【链接】

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"); } } }

 

转载请注明原文地址: https://www.6miu.com/read-4050208.html

最新回复(0)