题解 P12056 [THUPC 2025 决赛] 石墨烯

meyi · 2025-04-10 10:18:01 · 题解

简单题，考虑二分答案。

假设当前二分的答案为 x，那么等价于在环形数组上，b_i 可以依次与 a_i,a_{i-1},\cdots,a_{i-x+1} 匹配，直接模拟即可，x 合法等价于所有匹配完成后有 \sum a\le k。由于每次匹配必定会让 a 或 b 中的某个数变为 0，因此匹配次数是 \mathcal O(n) 的，总时间复杂度 \mathcal O(n\log n)。

为什么不考虑同时移动而这样贪心是对的？因为在这种贪心方式下，满足 j<i 的 a_j 必定会先于 a_i 去和 a_j,a_{j-1},\cdots,a_{i-x+1} 匹配，j>i 时同理，a_i 必定会先于 a_j 去和 a_i,a_{i-1},\cdots,a_{j-x+1} 匹配，也就是说我们并没有破坏同时移动的匹配顺序。

代码：

#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#define ALL(v) v.begin(),v.end()
#define For(i,_) for(int i=0,i##end=_;i<i##end;++i) // [0,_)
#define FOR(i,_,__) for(int i=_,i##end=__;i<i##end;++i) // [_,__)
#define Rep(i,_) for(int i=(_)-1;i>=0;--i) // [0,_)
#define REP(i,_,__) for(int i=(__)-1,i##end=_;i>=i##end;--i) // [_,__)
typedef long long ll;
typedef unsigned long long ull;
#define V vector
#define pb push_back
#define pf push_front
#define qb pop_back
#define qf pop_front
#define eb emplace_back
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
#define fi first
#define se second
const int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}},inf=0x3f3f3f3f,mod=1e9+7;
const ll infl=0x3f3f3f3f3f3f3f3fll;
template<class T>inline bool ckmin(T &x,const T &y){return x>y?x=y,1:0;}
template<class T>inline bool ckmax(T &x,const T &y){return x<y?x=y,1:0;}
int init=[](){return cin.tie(nullptr)->sync_with_stdio(false),0;}();
int main(){
    int t_case=1;
    scanf("%d",&t_case);
    while(t_case--){
        ll m;
        int n;
        scanf("%d%lld",&n,&m);
        V<int>a(n);
        for(int &i:a)scanf("%d",&i);
        V<int>b(n);
        for(int &i:b)scanf("%d",&i);
        auto check=[&](int k){
            V<int>c=a,d=b;
            deque<int>q;
            For(i,n){
                q.pb(i);
                int &x=d[i];
                while(q.size()&&x>=c[q.back()]&&i-q.back()<k)x-=c[q.back()],c[q.back()]=0,q.qb();
                if(q.size()&&i-q.back()<k)c[q.back()]-=x,x=0;
            }
            For(i,k){
                int &x=d[i];
                while(q.size()&&x>=c[q.back()]&&n+i-q.back()<k)x-=c[q.back()],c[q.back()]=0,q.qb();
                if(q.size()&&n+i-q.back()<k)c[q.back()]-=x,x=0;
            }
            ll y=0;
            for(int i:q)y+=c[i];
            return y<=m;
        };
        int ans=-1,l=0,r=n;
        while(l<=r){
            int mid=l+r>>1;
            if(check(mid))ans=mid,r=mid-1;
            else l=mid+1;
        }
        printf("%d\n",ans);
    }
    return 0;
}