首页 > 代码库 > 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;}
HDU 5073
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。