牛牛的战役 链接：https://ac.nowcoder.com/acm/problem/21613 来源：牛客网
牛牛逐渐成长，战斗力也渐渐增加，并可以指挥若干个oier协同作战 给你一个数组a表示我方每个人的战斗力 再给你一个数组b
再给你一个数组c
c[i]表示敌方b[i]战斗力的人有c[i]个
每个oier每次可以选择一名敌方人员进行战斗，如果战斗力大于等于敌方人员，就可以战胜，经验值+1
最开始的时候每个人的经验值都是0
现在牛牛想要打败所有敌方人员，也就是说每个敌方人员都要被一个oier所打败
但是牛牛想要最小化最大的经验值
如果不能打败所有的敌方人员，输出-1
否则输出最小化最大的经验值 输入 3 2 3 5 3 1 3 4 2 9 4 输出 7
可以二分可以贪心的一道题。 因为当初是通过标签贪心搜索到的这道题目，所以自己没有去写二分去尝试了贪心，同学去写了二分。 先说说二分，二分可以解决一类题型，就是最大值最小，或者最小值最大。这道题之中就有这一点，题目要求是最小化最大的经验值。这一点就契合了二分的条件，每次去二分答案，也就是去二分最后的经验最大值，然后去计算。如果计算出来的经验最大值小于当前尝试的二分结果，那么就可以往小区间（l=mid-1）方向，否则就往大区间方向。
我们再讲讲贪心，想要最大值最小，那么最优的策略就是平均分，如果一个oier打败的敌人超过了平均值，那么就可以请能力值大于这个oier的其它oier来帮忙，从而进行分担，达到减少最大值的目的。这里我们使用top变量来表示这个平均值。为了方便实现，需要对oier的能力值和敌人的能力值进行排序。然后从能力最小的oier开始贪心，每次都先计算一个平均值。如果当前oier能击败敌人，并且经验不大于平均值，那么就让这个oier继续去击败下一个强度的敌人（如果这个oier可以的话，也就是oier能力值大于下一个敌人，否则就使用下一个oier）。 但是这个强度的敌人全部由这个oier来击败后，大于了平均值，那么我们就需要操作一下，只让这个oier击败敌人后到达平均值就停止，不能继续。然后换下一个oier继续上述的操作，每次都计算一下最大值。最后输出答案。
#include<cstdio> #include<iostream> #include<cmath> #include<vector> #include<stack> #include<cstring> #include<queue> #include<algorithm> using namespace std; typedef long long ll; ll n,m,sum=0,maxxa=0,maxxb=0; ll a[56]; struct node { ll val; ll cou; }; struct node b[56]; bool cmp(struct node x,struct node y){ return x.val<y.val; } int main(){ #ifdef LOCAL freopen(".\\a.in", "r", stdin); #endif scanf("%lld",&n); for(int i=1;i<=n;i++){ scanf("%lld",&a[i]); maxxa=max(a[i],maxxa); } scanf("%lld",&m); for(int i=1;i<=m;i++){ scanf("%lld",&b[i].val); maxxb=max(maxxb,b[i].val); } for(int i=1;i<=m;i++){ scanf("%lld",&b[i].cou); sum+=b[i].cou; } if(maxxa<maxxb){//无法击败所有敌人 printf("-1\n"); return 0; } sort(a+1,a+n+1); sort(b+1,b+m+1,cmp); ll ans=0; int nowb=1; for(int i=1;i<=n;i++){ ll top=sum/(n-i+1);//平均值 ll tmp=0;//当前oier已经击败的敌人数量 while(a[i]>=b[nowb].val&&nowb<=m){//如果当前oier可以击败敌人 if(tmp+b[nowb].cou>top){//击败敌人后会超过平均值 b[nowb].cou=b[nowb].cou-(top-tmp); sum-=(top-tmp); tmp=top; break; } else {//不会超过平均值，就将所有敌人都击败 tmp+=b[nowb].cou; sum-=b[nowb].cou; b[nowb].cou=0; nowb++; } } ans=max(ans,tmp); } printf("%lld\n",ans); return 0; }