E. Carrots for Rabbits
给出n<1e5个萝卜每个萝卜的长度为$a_i$<1e6
现在要分给k个兔子(k>=n&&k<1e5) 你能将萝卜切成长度不同的小份
使得每个兔子能分到一段萝卜
它们吃萝卜所消耗的时间为其分到萝卜长度的平方即$len^2$
求它们吃萝卜所消耗的时间和(注意是$∑len_i^2$)最少是多少
参考官方题解
首先定义一个函数$f(len,pieces)$
表示将一根长度为len的胡萝卜分成pieces份 后给兔子吃所需的最小总时间
- 对于一根萝卜如何求它的$f(len,pieces)$ ？
当pieces=2,我们分成等长的两段(或长度尽量接近)所需的总时间最小
当pieces=3,我们分成等长的三段(或长度尽量接近)所需的总时间最小
因为$f(len,pieces)=∑_i^{pieces} len_i^2$ 最长的那段取平方后总会产生较大的时间消耗
所以直觉上均分能获得最优解(所需总时间最小)
- 这个规律即：对一个sum分成若干份每份取等次幂(推测)求和总是均分更优
我们需要切k-n刀才够每个兔子分 每次切能减小总时长最大的那个萝卜
即$f(len,pieces)-f(len,pieces+1)$ 最大的那个萝卜
于是用优先队列每次切一刀取出$f(len,pieces)-f(len,pieces+1)$最大的那个萝卜
到这里这题就可以解决了
但是题解中提到$f(l,p−1)−f(l,p)≥f(l,p)−f(l,p+1) $
其含义是 对同一根萝卜多次切 所能减少的总时间是非增的 (逐渐减少)
用数字表示就是8可以分成4 4和2 2 2 2
8 -> 4 4 减少的总时间小于 4 4 -> 2 2 2 2 减少的时间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define P pair<ll,int>
#define Turnoff std::ios::sync_with_stdio(false)
const ll Max=1e5+5;
const int Mod=998244353;
int n,k;
ll arr[Max],Pi[Max],NeedTime[Max];
ll cut(int len,int pieces){
ll Newlen=len/pieces;
ll Pieces_NewlenAddone=len%pieces;
ll Pieces_Newlen=pieces-Pieces_NewlenAddone;
ll tot=Newlen*Newlen*Pieces_Newlen+(Newlen+1)*(Newlen+1)*Pieces_NewlenAddone;
return tot;
}
int main() {
Turnoff;
cin>>n>>k;
ll sum=0;k=k-n;
priority_queue<P,vector<P>,less<P> >q;
for(int i=0;i<n;i++){
cin>>arr[i];Pi[i]=1;
sum+=arr[i]*arr[i];
q.push({arr[i]*arr[i]-cut(arr[i],2),i});
NeedTime[i]=cut(arr[i],2);
}
while(k--){
P temp=q.top();q.pop();
int i=temp.second;ll cost=temp.first;
sum-=cost;Pi[i]++;
q.push({NeedTime[i]-cut(arr[i],Pi[i]+1),i});
NeedTime[i]=cut(arr[i],Pi[i]+1);
}
cout<<sum<<endl;
}
|