卡牌

题目 卡牌

image-0155d527

思路分析

贪心或者二分

这里用二分写 假设能套出n套牌 那意味着每个牌都要能达到n个 即各个牌修改的次数和总修改次数是限制 如果能达到 说明凑得出 答案可能是它 也可能在右边 所以l=mid 如果凑不出 说明取大了 答案在左边 r=mid-1

注意数据范围很恶心 直接#define int long long

卡牌

代码实现

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

#define int long long

// typedef long long LL;

const int N=2e5+10,M=N*N;

int 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;

}

signed 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];

    int l=0,r=M;

    while(l<r){

        int mid=l+r+1>>1;

        if(check(mid))  l=mid;

        else    r=mid-1;

    }

    cout<<r<<endl;

    return 0;

}

同类题型

视频讲解

⬅️ 钟表 🏠 00-冲刺国赛 ➡️ 最大数字