题目描述：
有一个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[100010],n,aa,cf,cm,m,sum[100010],tot; int check(long long high,long long remain,int now) { if(high>aa) return 0; int pos=lower_bound(a+1,a+n+1,high)-a; if(pos>n-now) pos=n-now+1; if(remain>=high*(pos-1)-sum[pos-1]) { return 1; } return 0; } int main() { scanf("%lld%lld%lld%lld%lld",&n,&aa,&cf,&cm,&m); for(int i=1; i<=n; i++) { scanf("%lld",&a[i]); } sort(a+1,a+n+1); while(a[n]==aa) { tot++; n--; } for(int i=1;i<=n;i++) { sum[i]=sum[i-1]+a[i]; } long long cnt=0,ans=0; long long l=1,r=1e9,mid,re=m-cnt; while(l<=r) { mid=(l+r)>>1; if(check(mid,re,0)) { l=mid; } else { r=mid-1; } if(r-l<=1) { r=check(r,re,0)?r:l; break; } } ans=r*1ll*cm+tot*1ll*cf; for(int i=1; i<=n; i++) { cnt+=aa-a[n-i+1]; if(cnt>=m) { break; } long long l=1,r=1e9,mid,re=m-cnt; while(l<=r) { mid=(l+r)>>1; if(check(mid,re,i)) { l=mid; } else { r=mid-1; } if(r-l<=1) { r=check(r,re,i)?r:l; break; } } ans=max(1ll*(i+tot)*cf+1ll*r*cm,ans); } printf("%lld ",ans); }
思路其实很简单，但是真的是细节很多啊QAQ