卡牌

题目 卡牌

思路分析

但是这样很明显 效率特别低 因为要不断做全体减1的操作这需要遍历整个数组 还不断需要检查0在哪里 对该位置进行补1操作 这也是需要遍历数组的 而n的范围是\(2*10^5\) 显然会超时

所以考虑一下优化：

这样倒显得合理了

或者逆向思维 先随便套一个答案 看能不能凑出来

凑出来 check——对于每种牌i，是否能通过现有的牌a[i]加上最多b[i]张手写牌（但总手写不超过m张），凑齐至少mid张。具体是，计算每种牌缺少的数量needed[i] = max(0, mid - a[i])，如果所有needed[i]的总和不超过m，并且每个needed[i]都不超过b[i]，那么可以凑齐

代码实现

贪心

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

typedef long long LL;
typedef pair<int,int> PII;
const int N=2e5+10;
priority_queue<PII, vector<PII>, greater<PII>> a;
int b[N];
int n;
LL m;

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=0;i<n;i++){
        int x;cin>>x;
        a.push({x,i});
    }
    for(int i=0;i<n;i++)    cin>>b[i];

    while(m){
        auto cur=a.top();a.pop();
        int curvalue=cur.first,curidx=cur.second;
        if(b[curidx]==0)
          	break;

        curvalue++;
        a.push({curvalue,curidx});
        b[curidx]--;
        m--;
    }
    cout<<a.top().first<<endl;
    return 0;
}

二分

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

typedef long long LL;
const int N=2e5+10,M=N*N;
LL a[N],b[N];
int n,m;

bool check(int x){
    int allneed=0;
    for(int i=0;i<n;i++){
        int curneed=max(x-a[i],0ll);
        if(curneed>b[i])    return false;
        if(allneed+curneed>m)   return false;
        allneed+=curneed;
    }
    return true;
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=0;i<n;i++)    cin>>a[i];
    for(int i=0;i<n;i++)    cin>>b[i];
    LL l=0,r=M;
    while(l<r){
        LL mid=l+r+1>>1;
        if(check(mid))  l=mid;
        else    r=mid-1;
    }
    cout<<r<<endl;
    return 0;
}

同类题型

视频讲解

⬅️ 剪绳子 🏠 00-刷题理模型 ➡️ 学生和导师