首页 > 代码库 > HDU 5073

HDU 5073

http://acm.hdu.edu.cn/showproblem.php?pid=5073

这题的关键是要把p点减重心位置 的 平方的那个式子展开,就可以O(n),开始ans初始化为1e18一直wa,改成1e19就A了

最大的部分是连续的,头尾指针一起移动就可以

#include <iostream>#include <cstdio>#include <cstring>#include <map>#include <algorithm>using namespace std;typedef __int64 ll;ll a[50005], sum[50005], sum2[50005];int main(){    int T;    scanf("%d", &T);    while(T--){        ll n, k;        scanf("%I64d %I64d", &n, &k);        for(int i = 1; i <= n; i++)            scanf("%I64d", &a[i]);         if(n == k || k == n - 1){            printf("0.0000000000\n");            continue;        }        sort(a + 1, a + n + 1);        memset(sum, 0, sizeof(sum));        memset(sum2, 0, sizeof(sum2));         sum[1] = a[1];         sum2[1] = a[1] * a[1];         for(int i = 2; i <= n; i++){            sum[i] = sum[i - 1] + a[i];            sum2[i] = sum2[i - 1] + a[i] * a[i];         }        double ans = 1e19;         for(int front = 1, rear = n - k; rear <= n; front++, rear++){            ll av = sum[rear] - sum[front - 1];             double res=  (n - k) * (sum2[rear] - sum2[front - 1]) + 1.0 * av * av - 2.0 * av * (sum[rear] - sum[front - 1]);             ans = min(ans, res);         }        printf("%.10lf\n", ans / (n - k));    }    return 0;}
View Code

 

HDU 5073