自动搬运

查看原文

来自洛谷，原作者为

	Purslane AFO

搬运于2025-08-24 23:10:46，当前版本为作者最后更新于2025-03-04 10:19:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Solution

如果 Bessie 选定了某些考试（$k$ 给定），Elsie 如何让 Bessie 获得最低的成绩呢？

显然 Elsie 会选择 $a_i+b_i$ 最大的 $k$ 场考试。

所以，我们可以将考试按照 $a_i+b_i$ 排序。Bessie 要选出若干场考试，在前 $k$ 场获得 $-b_i$ 的分数，后若干场获得 $a_i$ 的分数。

贪心的，后若干场的 $a_i$ 应该全选，而前若干场的 $b_i$ 应该选前 $k$ 小的。

因此你可以得到一个 $O(n \log n)$ 单组询问的方法——从前往后扫描，维护前缀的 $b$ 的前 $k$ 小的和。

当然你也可以 DP。设 $dp_{i,j}$ 为，考虑了位置 $\ge i$ 的数，选了 $j$ 场考试给 Elsie 攻击你能获得的最大代价。

转移是容易的：

$dp_{i,0} = dp_{i+1,0} + a_i$，$dp_{i,j} = \max\{dp_{i+1,j},dp_{i+1,j-1}-b_i\}$。

显然 $dp_{i,*}$ 是单调递减的。看起来不太好优化，那就上 Slope Tricks！

打表发现，$dp_{i,*}$ 的差分数组是单峰的。虽然没有凹凸性，但是总比啥都没有强。画一个示意图：

先考虑优化 $dp_{i,j} = \max\{dp_{i+1,j},dp_{i+1,j-1}-b_i\}$。

这相当于什么呢？如果 $dp_{i+1,j-1} - dp_{i+1,j} \ge b_i$，就从 $(i+1,j-1)$ 转移到 $(i,j)$；否则从 $(i+1,j)$ 转移到 $(i,j)$。

发现这样的 $j$ 是一段前缀和后缀。所以我们使用 multiset 维护两个部分的差分数组，容易发现每次只有 $O(1)$ 个位置的差分发生变化（这里是 slope tricks 的基础操作，不赘述）。

使用数学归纳法也确实能够证明，差分数组一直是单峰的。

注意修改两个 multiset 的时候，如果修改的是最靠近拐点的差分，要注意判断单调性是否仍然成立，要将 $O(1)$ 个元素所在的集合进行微调。

细节有点多，场上调了整整一个小时。 /tuu

#include<bits/stdc++.h>
#define int long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=2e5+10;
int n,q,a[MAXN],b[MAXN],suf[MAXN],ans[MAXN];
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>q;
	vector<pair<int,int>> vc;
	ffor(i,1,n) cin>>a[i]>>b[i],vc.push_back({a[i],b[i]});
	sort(vc.begin(),vc.end(),[](pair<int,int> A,pair<int,int> B) {return A.first+A.second>B.first+B.second;});
	ffor(i,1,n) a[i]=vc[i-1].first,b[i]=vc[i-1].second;
	multiset<int> d1,d2;
	d1.insert(a[n]+b[n]);
	roff(i,n-1,1) {
		int flg=0;
		if(*d1.begin()<b[i]) flg=1;
		if(!flg) {
			d1.insert(a[i]+b[i]);
			continue ;	
		}
		flg=0;
		if(*(--d1.end())>b[i]) flg=1;
		if(!d2.empty()&&*(--d2.end())>b[i]) flg=1;
		if(!flg) {
			int m=*(--d1.end());
			d1.erase(--d1.end());
			d1.insert(m+a[i]);
			d2.insert(b[i]);
			if(*d2.begin()<*d1.begin()) d1.insert(*d2.begin()),d2.erase(d2.begin());
			continue ;	
		}
		if(*(--d1.end())<=b[i]) {
			d2.insert(b[i]);
			int m=*(--d1.end());
			d1.erase(--d1.end());
			d1.insert(m+a[i]);
			if(*d2.begin()<*d1.begin()) d1.insert(*d2.begin()),d2.erase(d2.begin());
			continue ;
		}
		auto it=d1.upper_bound(b[i]);
		int c=*prev(it),ov=*it;
		d1.erase(prev(it)),d1.insert(c+ov-b[i]),d1.erase(d1.find(ov)),d1.insert(a[i]+b[i]),d2.insert(b[i]);
		if(*d2.begin()<*d1.begin()) d1.insert(*d2.begin()),d2.erase(d2.begin());
	}
	int tot=0;
	ffor(i,1,n) tot+=a[i];
	ffor(i,0,n) {
		ans[i]=tot;
		if(!d1.empty()) tot-=*(--d1.end()),d1.erase(--d1.end());
		else if(!d2.empty()) tot-=*(d2.begin()),d2.erase(d2.begin());	
	}
	ffor(i,1,q) {
		int k;
		cin>>k;
		cout<<ans[k]<<'\n';	
	}
	return 0;
}