---
title: "卡牌"
created: 2025-11-28
tags:
  - 算法
---

# 卡牌

## 题目 [卡牌](https://dashoj.com/d/lqbG1/p/2)

![[image-266e2184.png]]

## 思路分析

![[image-34fc7c4a.png]]

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

所以考虑一下优化：

![[image-df83e660.png]]

这样倒显得合理了

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

如果能 说明答案可能是它也可能还能往大了凑 如果凑不出来 说明套大了 答案在左边 显然有二段性 而且是模板1 :  ------|
   ------

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

## 代码实现

**贪心**

```cpp
#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;
}
```

**二分**

```cpp
#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-刷题理模型]] ➡️ [[学生和导师|学生和导师]]