P8800 [蓝桥杯 2022 国 B] 卡牌

P8800 [蓝桥杯 2022 国 B] 卡牌

分析

“最多” -- 二分

1.二分区间（凑齐的卡牌套数）：

l：a[]min；r：(a[]+b[])max

2.check(x)：

（1）for循环内：

判断x - a[i] <= b[i]（对于 i 种牌，假设把空白牌用完，是否能凑齐x套）

        Y：定义一个变量，加上x - a[i]（对于第 i 种牌，凑齐x套需要的空白牌数）

        N：return false;

（2）判断需要的空白牌是否超出题目给的范围（if(s <= m)）

        s <= m：

                        s == m：ans = mid

                        s < m：l = mid + 1

        s > m：

                        r = mid - 1

代码 

注意：一定一定一定记得开long long.....

scanf("%lld")！！！

#include<iostream>
using namespace std;typedef long long ll;
const int N = 200010;
int a[N],b[N],n;
ll m;bool check(int x)
{ll s = 0;for(int i = 0;i < n;i ++){if(x - a[i] <= b[i]){if(x - a[i] > 0) s += (x - a[i]);}else return false;}if(s <= m) return true;else return false;
}int main()
{int l = 0x3f3f3f3f,r = 0;scanf("%d %lld",&n,&m);for(int i = 0;i < n;i ++){scanf("%d",&a[i]);l = min(l,a[i]);}for(int i = 0;i < n;i ++){scanf("%d",&b[i]);r = max(r,a[i] + b[i]);}int ans = 0;while(l <= r){int mid = l + r >> 1;if(check(mid)){ans = mid;l = mid + 1;}else r = mid - 1;}printf("%d",ans);return 0;
}