思维题+贪心——牛客多校第一场C

以你之姓@ 2023-10-11 09:10 44阅读 0赞

/* 给定一组n维向量 A=(a1/m,a2/m,a3/m ... an/m), 求另一个n维向量 P=(p1,p2,p3...pn),满足sum{pi}=1,使得ans=sum{(ai/m-pi)^2}最大化 并求出这个ans 首先将ai放大m倍 A=(a1,a2,a3...an) 同理 P=(p1,p2,p3...pn),sum{pi}=m 将ai按照降序排序，可以推出大的数减掉x一定比小的数减掉x更优 (ai^2-(ai-x)^2)-(aj^2-(aj-x)^2) =2*x*ai-x^2-(2*x*xj-x^2) =2*x*(ai-aj)>0 可以将原问题转化为从a[]数组里减去总和为m的数，使得最后a[]的平方和最小 那么我们按照贪心策略进行减法，首先将a1减成a1==a2,然后再将a1a2减成a1==a2==a3,依次类推,直到m不够用 最后答案就是减法完成后的a[]的平方和,并在除以m*m即可 
    */
    while(~scanf("%d%d", &n, &m)) {
            for(int i = 1; i <= n; ++i) {
                scanf("%d", &a[i]);
            }
            sort(a + 1, a + n + 1, [](int a, int b){
        return a > b;});
            int idx = n;
            int las = m;
            for(int i = 1; i < n; ++i) {
                if(i * abs(a[i+1] - a[i]) > las) {
                    idx = i;
                    break;
                } else {
                    las -= i * abs(a[i+1] - a[i]);
                }
            }
            LL num1 = 1LL * (idx * a[idx] - las) * (idx * a[idx] - las);
            LL num2 = 1LL * idx * m * m;
            for(int i = idx + 1; i <= n; ++i) {
                num1 += 1LL * a[i] * a[i] * idx;
            }
            LL tmp = __gcd(num1, num2);
            num1 /= tmp, num2 /= tmp;
            if(num2 == 1) printf("%lld\n", num1);
            else printf("%lld/%lld\n", num1, num2);
        }

转载于:https://www.cnblogs.com/zsben991126/p/11272986.html