【题目描述】：
肥料掺了金坷垃,一袋能顶两袋撒。来自美国的金坷垃是美国肥料研究中心CNT的最新科技成果。金坷垃像胶水,能使肥料转化为活肥,活力增加,肥力增大;
现在，你有n亩的小麦地需要增产，你拥有一些金坷垃，但是金坷垃极其稀少，掺肥料也只够你撒K次。
众所周知，金坷垃能激活土壤深处的氮磷钾，同一块地可以撒多次肥料，但是效果是有略微衰减的。
实地考察后你发现，第i亩土地第x次撒肥料增产a[i]-x+1公斤。
hzwer将代替你去撒肥料，但是他是个蒟蒻，完全不动大脑，所以你想知道如果他随机撒肥料，最坏情况下小麦将增产多少，最好情况下将增产多少？(他最多只会对第i亩地撒肥料a[i]次)
【输入描述】：
第一行两个整数n，K
第二行n个整数，第i个整数为a[i]
【输出描述】：
输出最大值，最小值，空格隔开
【样例输入】：
5 1010 3 3 1 2
【样例输出】：
58 26
【样例解释】：
第1亩撒8次增产52，第2亩撒1次增产3，第3亩撒1次增产3,总增产58。
最小值自己推。
【时间限制、数据范围及描述】：
时间：1s 空间：128M
对于30%的数据n，k<=1000
对于70%的数据n，k<=200000
对于100%的数据n，k，a[i]<=1000000
弄了半天，终于用了一种不是标解的思路。。。
不过如果把 sort 换成 桶 的话应该会更快些
附代码：
#include<iostream>#include<algorithm>#include<cstdio>#define MAXN 1000010using namespace std;int n,m,k,s=1,last,now,a[MAXN];long long ans1=0,ans2=0;inline int read(){int date=0,w=1;char c=0;while(c!='-'&&(c<'0'||c>'9'))c=getchar();if(c=='-'){w=-1;c=getchar();}while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}return date*w;}bool cmp(const int &g,const int &z){return g>z;}int main(){n=read();k=read();m=k;for(int i=1;i<=n;i++)a[i]=read();sort(a+1,a+n+1,cmp);now=a[1];last=2;for(;;k-=s,now--){while(now==a[last]){s++;last++;}if(k<s)break;ans1+=(long long)now*s;}ans1+=k*now;for(int i=n;i>=0&&m;i--){if(a[i]<=m){m-=a[i];ans2+=(long long)(1+a[i])*a[i]/2;}else{for(int j=1;j<=m;j++)ans2+=(long long)a[i]-j+1;m=0;}}printf("%lld %lld\n",ans1,ans2);return 0;}
如果觉得《肥得更高》对你有帮助，请点赞、收藏，并留下你的观点哦！
