蓝桥杯2022年第十三届决赛真题-卡牌-两种思路（二分+暴力枚举）

解题思路:

思路1：暴力枚举

先把数组从小到大排序，然后先从小的开始凑套。

思路2：二分枚举

二分枚举可以凑成mid套

注意事项:

需要开longlong

参考代码:

暴力枚举：

#include <bits/stdc++.h>
#define pii pair<int, int>
#define x first
#define y second 
#define ll long long
using namespace std;
const int N  = 2e5 + 10;
ll n, m;
ll a[N], b[N];

//暴力 
int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i++)cin >> a[i];
    ll mi = 1e18;
    for(int i = 0; i < n; i++){
        cin >> b[i];
        mi = min(b[i] + a[i], mi); // 最少能合成的套数 
    }
    sort(a, a + n);//从小到大排序 
    ll res = 0;
    for(int i = 0; i < n; i++){
        int j = i+1;
        while(j < n && a[j] == a[i]){//牌号一样的 
            j++;
        }
        if(i == 0)res = a[i];//最少已经有的套数 
        else{
//            cout << m << ' ' << res << ' ' << j << '\n';
            if(m - (a[i] - a[i-1]) * (ll)i >= 0){//该号数前所有牌号都增加到当前牌号的套数 
                m -= (a[i] - a[i-1]) * (ll)i;
                res += (a[i] - a[i-1]);
            }else{
                res += m / i; // 没有这么多牌 
                m = 0;
                break;
            }
        }
        i = j - 1;
    }
//    cout << res << ' ' << m << ' ' << n << '\n';
    res += m / n;//剩下的牌 
    cout << min(mi, res);
    return 0;
}

二分枚举：

#include <bits/stdc++.h>
#define pii pair<int, int>
#define x first
#define y second 
#define ll long long
using namespace std;
const int N  = 2e5 + 10;
ll n, m;
ll a[N], b[N];

//二分
bool check(ll mid){
	ll add = 0;
	for(int i = 0; i < n; i++){
		if(mid > a[i] && mid - a[i] > b[i]){
			return false;
		}
		if(mid > a[i])add += mid - a[i];
		if(add > m)return false;
	}
	return true;
} 

int main(){
	cin >> n >> m;
	ll mi = 1e18;//最少已经能凑成mi套
	for(int i = 0; i < n; i++){
		cin >> a[i];
		mi = min(mi, a[i]);
	}
	for(int j = 0; j < n; j++)cin >> b[j];
	
	ll l = mi, r = 1e18, mid, res;
	while(l <= r){
		mid = l + r >> 1;
//		cout << l << ' ' << r << ' ' << mid << '\n';
		if(check(mid)){
			l = mid + 1;
		}else{
			r = mid - 1;
		}
	}
	cout << l - 1 << '\n';
	return 0;
}