CF 1428E Carrots for Rabbits

题目描述

http://codeforces.com/problemset/problem/1428/E

Solution

对于一块萝卜，如果要切成 $k$ 份，那么这 $k$ 份的大小差距不能超过 $1$

考虑最后的答案组成一定是一开始的萝卜分别被切成了若干份

另外我们再次考虑对于一个萝卜，切成 $k$ 份的变成 $k+1$ 的收益是随着 $k$ 的增加而减小的

然后这东西就是超级钢琴了

另外对于上面那个结论的证明，我们令 $f(l,p)$ 表示把长度为 $l$ 的萝卜切成 $k$ 份的平方和

显然我们有 $f(l,p-1)+f(l,p+1)\ge f(2l,2p)=2f(l,p)$

时间复杂度 $O(k\log n)$

#include <iostream>
#include <cstdio>
#include <queue>
#define maxn 100010
#define cQ const Queue
#define ll long long 
using namespace std;

int n, m, a[maxn];

inline ll calc(int k, int v) {
    int res = v % k; 
    return 1ll * res * (v / k + 1) * (v / k + 1) + 1ll * (k - res) * (v / k) * (v / k);
} 

struct Queue {
    int k, v;

    Queue(int _k = 0, int _v = 0) { k = _k; v = _v; }

    friend bool operator < (cQ &u, cQ &v) {
        return calc(u.k, u.v) - calc(u.k + 1, u.v) < calc(v.k, v.v) - calc(v.k + 1, v.v); 
    } 
}; priority_queue<Queue> Q; 

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i]; Q.push(Queue(1, a[i]));
    }
    for (int i = 1; i <= m - n; ++i) {
        Queue u = Q.top(); Q.pop();
        Q.push(Queue(u.k + 1, u.v));
    } ll ans = 0; 
    while (!Q.empty()) {
        Queue u = Q.top(); Q.pop();
        ans += calc(u.k, u.v);
    } cout << ans << endl; 
    return 0;
}