题目描述：
有一个oier，他有n个算法技能，每个技能有一个水平值，每个技能的水平上限都是A，设这个oier有cnt个技能达到了A, 设所有水平值的最小值为mi,那么这个oier的战斗力为cnt×Cf+mi×Cm,现在这个oier准备去提升自己的技能，他有m次提升的机会，每次提升可以选择某一个技能给水平值加1，如何分配这些提升的机会，来使得自己的战斗力总值最大？
输入格式：
第一行输入5个整数,n,A,Cf,Cm,m
第二行输入n个整数，表示每个技能的水平值
输出格式：
输出最大战斗力值
样例输入：
3 5 10 1 5
1 3 1
样例输出：
12
约定：
1≤n≤100000,1≤A≤10^9,0≤Cf,Cm≤1000,0≤m≤10^15
题解：考虑贪心的策略，由于只有将一个技能点到A或者提升最低技能等级才能增加战斗力，所以说，只有两种操作是有意义的
1.将一个技能点到A
2.将所有最低等级的技能都点高一级，相当于提升最低等级一级
所以我们可以从1-n枚举将i个技能点到a级所需要的最小花费，这个东西sort一下就能搞了，显然点满最大的前i个花费最小，然后用剩下的技能点高最低技能，其思路就相当于把剩下的水倒进低洼，去获得此时水的高度一样
这个高度显然是可以二分的
用lower_bound搞出高度大于等于high的第一个位置pos，然后显然pos-1位置都是要填的，至于要填多少，显然可以维护一个前缀和记录已经填了多少了，再用high*(pos-1)-这个数就可以知道你要填多少，然后和你还剩的数比下哪个大就知道了，这东西是单调的，所以可以二分
不过要注意如果你已经把i个数点到A了，那么pos的最大位置也就是n-i了
其次开局已经到A的技能还要特殊处理一下
代码如下：
#include<deque>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define mod 1000000007
using namespace std; long long a[],n,aa,cf,cm,m,sum[],tot; int check(long long high,long long remain,int now)
{
if(high>aa) return ;
int pos=lower_bound(a+,a+n+,high)-a;
if(pos>n-now) pos=n-now+;
if(remain>=high*(pos-)-sum[pos-])
{
return ;
}
return ;
} int main()
{
scanf("%lld%lld%lld%lld%lld",&n,&aa,&cf,&cm,&m);
for(int i=; i<=n; i++)
{
scanf("%lld",&a[i]);
}
sort(a+,a+n+);
while(a[n]==aa)
{
tot++;
n--;
}
for(int i=;i<=n;i++)
{
sum[i]=sum[i-]+a[i];
}
long long cnt=,ans=;
long long l=,r=1e9,mid,re=m-cnt;
while(l<=r)
{
mid=(l+r)>>;
if(check(mid,re,))
{
l=mid;
}
else
{
r=mid-;
}
if(r-l<=)
{
r=check(r,re,)?r:l;
break;
}
}
ans=r*1ll*cm+tot*1ll*cf;
for(int i=; i<=n; i++)
{
cnt+=aa-a[n-i+];
if(cnt>=m)
{
break;
}
long long l=,r=1e9,mid,re=m-cnt;
while(l<=r)
{
mid=(l+r)>>;
if(check(mid,re,i))
{
l=mid;
}
else
{
r=mid-;
}
if(r-l<=)
{
r=check(r,re,i)?r:l;
break;
}
}
ans=max(1ll*(i+tot)*cf+1ll*r*cm,ans);
}
printf("%lld\n",ans);
}
思路其实很简单，但是真的是细节很多啊QAQ