自动搬运

查看原文

来自洛谷，原作者为

	gcwixsxr lxyddd

搬运于2025-08-24 22:15:32，当前版本为作者最后更新于2020-09-11 09:10:16，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这是一道比较经典的反悔贪心。原来CTSC还有这样的水题。

什么是反悔贪心呢？用通俗的话讲，由于贪心只注重当前的最优解，有时候无法得到全局最优解。反悔贪心就是在发现比当前最优解还要优时进行反悔操作。

看到这道题，题意大致可以理解为：给你 $N$ 个区间，规定区间的的长度为 $W_i$ ,左端点不能超过 $C_i$ ，要使得区间个数最多，并且使得区间长度之和最小。

这里我们不妨定义一个数组 $R_i$ ，表示第 $i$ 个区间的右端点不超过 $R_i$ ，$R_i$ 在数值上等于 $C_i+W_i$ ，那么贪心策略又是什么？

我们不妨设 $R_1 \leq R_2 \leq R_3 \leq \dots \leq R_N$ ,此时我们已经选出了满足要求的若干个区间，记这些区间的长度总和为 $S$ ，区间长度的最大值为 $MAX$ ，现在循环到了第 $k$ 个区间，如果发现 $S+W_k \leq R_k$ ，那么代表当前区间可以被选择，则区间个数加一，区间长度加 $W_k$ ，否则，如果$S+W_k > R_k$，那么代表当前区间就没有用了吗？不对，因为题目还有一个条件——要使区间长度之和最小。为了使每一个区间都物尽其用，我们还可以将 $W_k$ 和 $MAX$ 相比较，如果 $W_k < MAX$，则可以将长度为 $MAX$ 的区间从原来满足要求的区间们中取出，重新插入当前的区间，还要记得更新区间的总长度。那如果 $W_k \geq MAX$呢？那这个区间是真的没用了。

说了一堆，反悔在哪呢，就是在取出长度为 $MAX$ 的区间，插入当前的区间中。一般贪心是没有这个操作的。为了取得全局最优值，只能舍弃掉一些相对更劣质的决策，加入更优质的决策。

最大值可以用堆来维护。

贴上代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+2;
#define int long long
struct interval{
	int len,r;
	bool operator <(const interval & x)const{
		return r<x.r;
	}
}a[MAXN];
int f[MAXN];
int n,num,sum;
priority_queue<int>qu;
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].r>>a[i].len;
		a[i].r+=a[i].len;
	}
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++){
		if(sum+a[i].len<=a[i].r){
			num++;
			sum+=a[i].len;
			qu.push(a[i].len);
		}
		else if(qu.top()>a[i].len){
			sum-=qu.top();
			qu.pop();
			qu.push(a[i].len);
			sum+=a[i].len;
		}
	}
	cout<<num<<endl<<sum<<endl;
	return 0;
}