无敌浩克

# 题意
n种牌,m张king ,每种牌有a[i] 张,每次可以并且只能使用1张king 代替任意一种,并且每套牌中只能用一张king,组成一套牌,问最多可以有套牌

# 题解
二分答案
Check 如果某种牌的数量少于当前二分的值,则最起码也要用king牌补充,才有可能组成x套牌,如果king牌全部用光后,仍有少于x张的牌,说明不合法

因为一套牌中不能出现两张king牌,所以还要进一步判断 一套牌中不能出现两张king牌,换言之就是每张king牌必须和其他的普通牌组合成为一套

king牌必须跟非king牌组 合,所以从其他种类中的普通牌减掉这种king牌的数量,最终如果所有的普通牌的数量都大于0说明合法

 1 #include <bits/stdc++.h>
 2 #define Max 1e9
 3 using namespace std;
 4 int a[55];
 5 int king[55];
 6 int n,m;
 7 int b[55];
 8 bool check(int x) {
 9     memset(king,0,sizeof king);
10     int lef=m;
11     memcpy(b, a, sizeof b);
12     for (int i = 1; i <= n; i++) {
13         if(x>b[i]) {
14             king[i] = x - b[i];
15             lef -= king[i];
16             if(lef<0) return 0;
17         }
18     }
19     for (int i = 1; i <= n; i++) {
20             for (int j = 1; j <= n; j++) {
21                 if(i!=j)
22                     b[j]-=king[i];
23                 if(b[i]<0) return 0;
24             }
25     }
26     return 1;
27 }
28 int main(){
29     ios::sync_with_stdio(0);
30     cin.tie(0);
31     cout.tie(0);
32     cin>>n>>m;
33     for(int i=1;i<=n;i++)
34         cin >> a[i];
35     int l=1,r=Max;
36     while(l<r){
37         int mid=(l+r+1)>>1;
38         if(check(mid))
39             l=mid;
40         else r=mid-1;
41     }
42     cout<<l<<endl;
43 }

 

 

上一篇:CF3A Shortest path of the king


下一篇:Hdu-5723 最小生成树+树上求和期望