题解：CF2089B2 Canteen (Hard Version)

Stupid_CCCat · 2025-03-26 14:00:24 · 题解

题意描述

给定两个长度为 n 的整数序列 a 和 b，保证 a 的元素和不超过 b 的元素和。需对 a 进行以下操作恰好 k 次：选择任意 a_i（满足 a_i > 0），使得 a_i=a_i-1。

之后按以下操作循环处理：

每轮操作流程：

对每个位置 i，对 a_i 和 b_i 同时减去 a_i 和 b_i 的较小值。
构造新序列 c，其中 c_i = a_{(i-1) \bmod n}。
将 c 复制给 a。

目标：找到经过恰好 k 次减操作后，使 a 全变为 0 所需的最少操作轮数。

解题思路

声明：以下序列下标均从 0 开始。

Easy Version

首先，我们容易证明经过至多 n 轮操作即可使 a 全变为 0，因为在经过 n 轮操作后，任意 a_i 和任意 b_i 都已匹配过一次，且 sum_a \leq sum_b。
考虑破环成链，将 a 与 b 都循环延长，即：a_i=a_{i-n}，b_i=b_{i-n}（n\leq i < 2n），那么我们可以发现，对于每个 a_i（0 \leq i < n），只可能和 b_j（i \leq j < i+n）匹配。
可以仿照括号匹配，将 a_i 当作左括号，对每个 b_i 我们优先和左边第一个不为 0 的 a_i 匹配。
从左到右枚举 i，将每个不为 0 的 a_i 入栈，然后 b_i 和不断和栈首的 a_j 匹配，直到栈空或者 b_i=0，匹配的同时更新最大操作轮数，因为 b_i 和 a_j 匹配需要经过 i-j+1 轮，即 ans=max(ans,i-j+1)。
为什么这样是正确的呢？可能有人会问：这是一个环，如果对于某个 b_i，前面所有的 a_j 都为 0，那应该从序列尾开始找最后一个不为 0 的 a_j 与当前 b_i 匹配呀。所以我们破环成链，当我们维护 a_j （j<n）和 b_i （i<n）时，我们需要同时维护 a_{j+n} 和 b_{i+n}，这样，当我们枚举到 b_{i+n}，它的意义和 b_i 是一样的，假设真的存在一个 a_j （i<j<n）和 b_i 匹配，这个 a_j 就会和 b_{i+n} 匹配上。
时间复杂度为 O(n)。

Hard Version

考虑二分答案，检查需要多少次a_i=a_i-1 的操作，才能使轮数不超过 mid。
设需要 ans 次操作，才能使轮数不超过 mid，ans 初始值为 0。
我们知道 b_i 和 a_j 匹配需要经过 i-j+1 轮，当 i-j+1>=mid 时，我们不能进行匹配了，所以当前的 a_j 就需要用初始的次数去将它减少到 0，即 ans+=a_j。
二分答案即可，时间复杂度为 O(nlogn)。

代码呈现

Easy Version

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

void solve()
{
    int n,k;
    cin>>n>>k;
    vector<int> a,b;
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        a.push_back(x);
    }
    for(int i=0;i<n;i++)
        a.push_back(a[i]);
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        b.push_back(x);
    }
    for(int i=0;i<n;i++)
        b.push_back(b[i]);
    stack<int> stk;
    int ans=0;
    for(int i=0;i<2*n;i++)
    {
        if(a[i])
            stk.push(i);
        while(!stk.empty()&&b[i])   
        {
            int now=stk.top();
            ans=max(ans,i-now+1);
            int minn=min(a[now],b[i]);
            b[i]-=minn,a[now]-=minn;
            if(i<n)
                b[i+n]-=minn,a[now+n]-=minn;
            if(a[now]==0)
                stk.pop();
        }
    }
    cout<<ans<<endl;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T=1;
    cin>>T;
    while(T--)
        solve();
}

Hard Version

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

int check(int n,int mid,vector<int> a,vector<int> b)
{
    stack<int> stk;
    int ans=0;
    for(int i=0;i<2*n;i++)
    {
        if(a[i])
            stk.push(i);
        while(!stk.empty()&&b[i])   
        {
            int now=stk.top();
            if(i-now+1>mid)
            {
                ans+=a[now];
                a[now]=0;
                if(now<n)
                    a[now+n]=0;
                stk.pop();
            }
            else
            {
                int minn=min(a[now],b[i]);
                b[i]-=minn,a[now]-=minn;
                if(i<n)
                    b[i+n]-=minn,a[now+n]-=minn;
                if(a[now]==0)
                    stk.pop();
            }
        }
    }
    return ans;
}
void solve()
{
    int n,k;
    cin>>n>>k;
    vector<int> a,b;
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        a.push_back(x);
    }
    for(int i=0;i<n;i++)
        a.push_back(a[i]);
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        b.push_back(x);
    }
    for(int i=0;i<n;i++)
        b.push_back(b[i]);
    int l=0,r=n;
    while(l<r)
    {
        int mid=(l+r)>>1;
        if(check(n,mid,a,b)>k)
            l=mid+1;
        else
            r=mid;
    }
    cout<<l<<endl;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T=1;
    cin>>T;
    while(T--)
        solve();
}