题解：P11663 [JOI 2025 Final] 勇者比太郎 2 / Bitaro the Brave 2

MonKeySort_ZYczc · 2025-08-06 16:23:48 · 题解

思路流程

直接处理很麻烦，先断环成链。
为习惯与下文叙述方便，假设断环成链后 A_{i+n}=A_i(i<n)，B 数组同理。
把 B_i 做前缀和，设前缀和数组为 S_i。
容易发现，假如第一个打的怪物是 i(1\le i\le n)，此时比太郎需要

的力量，将式子化为

再化为

发现，A_j-S_{j-1} 是不随 i 变化的，因此提前处理，让 A_j:=A_j-S_{j-1}。
此时问题转化为定长区间最大值问题，单调队列解决就行。
答案即为

。

总时间复杂度：O(n)。

哦对了，别忘开 long long 了。

代码实现

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int N=1e6+10;
int n,a[N],b[N],que[N<<2][2],head=1,tail,ans=0x3f3f3f3f3f3f3f3fll;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],a[i+n]=a[i];
    for(int i=1;i<=n;i++) cin>>b[i],b[i+n]=b[i];
    for(int i=1;i<2*n;i++) a[i]-=b[i-1],b[i]+=b[i-1];
    for(int i=1;i<n;i++) 
    {
        while(head<=tail&&que[tail][1]<=a[i]) tail--;
        tail++;que[tail][0]=i;que[tail][1]=a[i];
    }
    for(int i=n;i<2*n;i++)
    {
        while(head<=tail&&que[head][0]<i-n+1) head++;
        while(head<=tail&&que[tail][1]<=a[i]) tail--;
        tail++;que[tail][0]=i;que[tail][1]=a[i];
        ans=min(ans,que[head][1]+b[i-n]);
        //cout<<que[head][1]+b[i-n]<<endl;
    }
    cout<<ans;
}