CF1918

flower1 · 2025-09-09 08:29:48 · 个人记录

CF1918

D

Solution

最大值最小，首先显然有二分答案。

观察阻断了一个点，能取到的上一个阻断的点显然是一个区间，进一步发现，其形如一个滑动窗口。

定义 f_i 为阻断了第 i 个点，前 i 个点被阻断权值和最小值。

其中 s_i 为 a 的前缀和，x 为当前二分的答案。

使用单调队列解决，时间复杂度 O(n \log nV)。

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int T,n,a[N],sum[N],f[N];
int q[N];
int read(){
    int k=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')
        ch=getchar();
    while(ch>='0'&&ch<='9')
        k=k*10+ch-'0',ch=getchar();
    return k;
}
bool check(int x){
    int l=1,r=0;
    for(int i=1;i<=n+1;i++){
        q[++r]=i-1;
        while(l<r&&f[q[r]]<=f[q[r-1]])
            q[r-1]=q[r],r--;
        while(l<=r&&sum[i-1]-sum[q[l]]>x)
            l++;
        f[i]=f[q[l]]+a[i];
    }
    return f[n+1]<=x;
}
signed main(){
    T=read();
    while(T--){
        n=read();
        for(int i=1;i<=n;i++)
            a[i]=read(),sum[i]=a[i]+sum[i-1];
        a[n+1]=0;
        int l=1,r=1e18;
        while(l<r){
            int mid=(l+r)>>1;
            if(check(mid))
                r=mid;
            else
                l=mid+1;
        }
        printf("%lld\n",l);
    }
    return 0;
}

E

Solution

由于 x 未知，首先可以花费 O(n) 次询问求出最大值位置 mx，最小值位置 mi。

这样我们就可以控制 x，询问 mx \to x+1，询问 mi \to x-1。

如果移动 x 无代价，那么对每个 i 单独二分求解即可，但移动 x 要花费代价，那么使用整体二分，即可解决本题。

Code

#include <bits/stdc++.h>
using namespace std;
const int N=2005;
int T,n,mi,mx,now,p[N],p1[N],p2[N],ans[N];
int ask(int x){
    cout<<"? "<<x<<endl;
    cout.flush();
    char c;
    cin>>c;
    if(c=='<'){
        now--;
        return -1;
    }
    else if(c=='=')
        return 0;
    else{
        now++;
        return 1;
    }
}
void change(int x){
    while(now<x) ask(mx);
    while(now>x) ask(mi);
}
void solve(int l,int r,int L,int R){
    if(l>r) return;
    if(l==r) ans[p[l]]=L;
    int mid=(L+R)>>1,cnt1=0,cnt2=0;
    change(mid);
    for(int i=l;i<=r;i++){
        int t=ask(p[i]);
        if(t==-1)
            p1[++cnt1]=p[i],ask(mx);
        else if(t==0)
            ans[p[i]]=mid;
        else
            p2[++cnt2]=p[i],ask(mi);
    }
    for(int i=l;i<=l+cnt1-1;i++)
        p[i]=p1[i-l+1];
    for(int i=l+cnt1+1;i<=r;i++)
        p[i]=p2[i-l-cnt1];
    solve(l,l+cnt1-1,L,mid-1);
    solve(l+cnt1+1,r,mid+1,R);
}
int main(){
    cin>>T;
    while(T--){
        mx=0,mi=0;
        cin>>n;
        int t;
        for(int i=1;i<=n;i++){
            t=ask(i);
            if(t==-1){
                if(mx!=0) ask(mx);
                continue;
            }
            else{
                mx=i;
                while(t!=0)
                    t=ask(i);
            }
        }
        for(int i=1;i<=n;i++){
            t=ask(i);
            if(t==1){
                if(mi!=0) ask(mi);
                continue;
            }
            else{
                mi=i;
                while(t!=0)
                    t=ask(i);
            }
        }
        t=ask(mi);
        while(t!=0)
            t=ask(mi);
        now=1;
        for(int i=1;i<=n;i++)
            p[i]=i;
        solve(1,n,1,n);
        cout<<"!";
        for(int i=1;i<=n;i++)
            cout<<" "<<ans[i];
        cout<<endl;
        cout.flush();
    }
    return 0;
}