CF2055E Haystacks 题解

zrl123456 · 2026-10-21 11:30:55 · 题解

:::::success[Hint 1] 我们考虑将此题分为两步来做，第一步是选定这些位置被删空的顺序，第二步是贪心求出操作数，那么我们考虑顺序已经被固定了怎么做。 ::::: :::::success[Hint 2] 考虑通过邻项交换法来找到顺序是什么。 :::::

对应 Hint 1：

我们考虑将此题分为两步来做，第一步是选定这些位置被删空的顺序，第二步是贪心求出操作数，那么我们考虑顺序已经被固定了怎么做。

我们考虑如果没有 b_i 贡献，我们将会进行下面的操作：

• 把第一个位置清空，清出来的放到后面去。
• 然后我们把后面的位置不断清空扔到前面去。

这种情况下显然答案是 a_1+\sum_{i=1}^na_i。

接下来加上 b_i 的贡献，这时我们发现某些位置可能会和第一个位置一样被迫把清出来的东西扔到后面去，那么我们至少要额外多操作 \max_{i=1}^n((\sum_{j=1}^ia_j)-(\sum_{j=1}^{i-1}b_j)) 次。

这个下界是可以取到的，我们被迫往后扔的时候扔到 n 号堆即可。

那么固定顺序下答案为：

对应 Hint 2：

我们考虑进行邻项交换法，我们假设我们要比较 (a_i,b_i) 和 (a_j,b_j)，如果我们想让 (a_i,b_i) 在前面，那么我们实际上就是要满足下面的式子：

这个条件我们是不能直接扔到 sort 里跑一遍的，因为它不是一个偏序关系，那么我们考虑进行一些适当的转化。

现在这个形式比较难看，不等式两边同时减掉 a_i+a_j，变为 \max(-a_j,-b_i)\le\max(-a_i,-b_j)，即 \min(a_i,b_j)\le\min(a_j,b_i)。

首先我们观察到，当 a_i\le b_i,a_j>b_j 的时候上式显然成立，也就是说所有 a_i-b_i\le 0 的要排在 a_j-b_j>0 的前面。

对于 a_i-b_i\le 0,a_j-b_j\le 0 的情况，我们将上式转化为 a_i\le a_j\land a_i\le b_i\lor b_j\le a_j\land b_j\le b_i，那么把前提条件套进去就转化为了 a_i\le a_j\lor b_j=a_j\land b_j\le b_i，那么我们按 a_i<a_j 排序不劣。

对于 a_i-b_i>0,a_j-b_j>0 的情况，同理可以得到 b_i>b_j。

然后我们考虑一下样例这个 -1 是怎么来的，我们发现这样我们必须满足 (\sum_{i=1}^na_i)-(\sum_{i=1}^{n-1}b_i)\le 0，那么我们考虑枚举出这些位置是哪些位置，然后将剩下 n-1 个位置按照原顺序拼接起来即可，我们可以预处理出来前后缀的最大值。

这样我们就做完了这道题。
时间复杂度为 \Theta(n\log n)，空间复杂度为 \Theta(n)。

:::::success[code]

#include<bits/stdc++.h>
#define inl inline
#define int long long
#define lll __int128
#define fst ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i,x,y) for(int i=x;i<=(y);++i) 
#define per(i,x,y) for(int i=x;i>=(y);--i)
#define rpr(i,x,y,z) for(int i=x;i<=(y);i+=z)
#define epe(i,x,y,z) for(int i=x;i>=(y);i-=z)
#define repe(i,x,y) for(i=x;i<=(y);++i) 
#define endl '\n'
#define INF 9e18 
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front 
#define fi first
#define se second
#define lcm(x,y) x/__gcd(x,y)*y
#define ull unsigned long long
#define prr make_pair
#define pii pair<int,int> 
#define gt(s) getline(cin,s)
#define at(x,y) for(auto x:y)
#define ff fflush(stdout)
#define mt(x,y) memset(x,y,sizeof(x))
#define idg isdigit
#define fp(s) string ssss=s;freopen((ssss+".in").c_str(),"r",stdin);freopen((ssss+\
".out").c_str(),"w",stdout);
#define sstr stringstream 
#define all(x) x.begin(),x.end()
#define mcy(a,b) memcpy(a,b,sizeof(b))
#define ui unsigned
#define si signed
#define eb emplace_back
#define pff(x) ((x)*(x))
#define eush emplace
#define double long double
#define pdi pair<double,int>
#ifdef __unix__
#define gc getchar_unlocked
#else
#define gc _getchar_nolock
#endif
#ifdef __unix__
#define pc putchar_unlocked
#else
#define pc _putchar_nolock
#endif
using namespace std;
const int N=5e5+5;
struct node{
    int a,b;
    inl node(){
        a=b=0;
    } 
    inl node(int a,int b):a(a),b(b){}
}a[N];
int mx[N],mx2[N],s[N];
inl void solve(){
    int n,sum=0,res=0,ans=INF;
    cin>>n;
    rep(i,1,n) cin>>a[i].a>>a[i].b;
    rep(i,1,n) sum+=a[i].a;
    rep(i,1,n) res+=a[i].b-a[i].a;
    sort(a+1,a+n+1,[&](node x,node y){
        if((x.a-x.b)*(y.a-y.b)<=0&&(x.a!=x.b||y.a!=y.b)) return x.a-x.b<=y.a-y.b;
        if(x.a<=x.b) return x.a<y.a;
        return x.b>y.b;
    });
    mx[0]=mx2[n+1]=-INF;
    rep(i,1,n) s[i]=s[i-1]+a[i].a-a[i-1].b;
    rep(i,1,n) mx[i]=max(mx[i-1],s[i]);
    per(i,n,1) mx2[i]=max(mx2[i+1],s[i]);
    rep(i,1,n)
        if(a[i].b<=res) ans=min(ans,max(mx[i-1],mx2[i+1]-a[i].a+a[i].b));
//  rep(i,1,n) cout<<a[i].a<<' '<<a[i].b<<endl; 
    if(ans!=INF) cout<<ans+sum<<endl;
    else cout<<-1<<endl;
}
si main(){
    fst;
    int t;
    cin>>t;
    while(t--) solve(); 
    return 'T'^'0'^'m'^'l'^'e';
}

:::::