自动搬运

查看原文

来自洛谷，原作者为

	meyi 明日黄花

搬运于2025-08-24 23:12:29，当前版本为作者最后更新于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;
}