【反悔贪心】P2949WorkSchedulingG+P4053[JSOI2007]建筑抢修题解

这两天遇到了几个很神奇的题目——能反悔的贪心。赶紧记录一下。

例1（用时一定模型）

用时一定：每个任务完成的耗时都是一样的。

题面：Luogu - P2949 Work Scheduling G

大体思路是：先把所有任务按照截止时间从小到大排序，然后枚举，遇到一个能做任务的就把他做了，把他的贡献加入一个小根堆中（贪心）；如果遇到一个任务不能做了，但它比之前做过的任务的收益更高（即大于小根堆的堆顶），就放弃堆顶的那个任务，做这个任务。
这样实现能保证答案最优。代码实现应该就很简洁明了了。

注：因为每完成一个工作需要的时间都是1，所以小根堆的size就是已经花费的时间。若任务i能完成，则Q.size()>a[i]的截止时间

Code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 7;

struct Node{
    int d, p; // 截止时间、获得收益
    friend bool operator < (Node p1, Node p2){
        return p1.d < p2.d; // 排序规则：按照截止日期从小到大排序
    }
}a[maxn];

void solve()
{
    int n; cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i].d >> a[i].p;
    sort(a + 1, a + n + 1);

    priority_queue <int, vector<int>, greater<int> > Q; // 小根堆，存储已完成任务的所有收益
    ll ans = 0; //! 开long long！！！
    for(int i = 1; i <= n; i ++){
        if(a[i].d > Q.size()){ // 不超时，正常加入
            Q.push(a[i].p);
            ans += a[i].p;
        }else{ // 超时的话，如果当前任务的报酬 大于 做完的任务报酬中最小的，就替换之前的任务
            if(a[i].p > Q.top()){
                ans -= Q.top(); Q.pop();
                ans += a[i].p;
                Q.push(a[i].p);
            }
        }
    }

    cout << ans << '\n';
}

signed main()
{
    ios :: sync_with_stdio(false), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}

例2（价值一定模型）

价值一定：每完成一个任务，获得的积分（价值）是一样的。

再来一题：Luogu - P4053 [JSOI2007] 建筑抢修

看完第一题之后，这道题应该会灵光乍现（即使这是一道蓝题？）。可以先按照任务截止时间 T 2 T_2 T2​ 升序排序。然后从小到大枚举，如果能修理就先修上，同时把修理它要花费的时间 T 1 T_1 T1​ 存到大根堆 Q Q Q 中。一旦遇到不能修上的，就把修复耗时最大的那个（即 Q.top()）报废掉，给后面的建筑留下机会。

在代码的主循环中，有人可能认为直接把当前的 a[i] 统计上答案会不妥，因为可能 a[i] 就是时间最长的那个。但如果是那种情况的话，a[i] 一定会成为 Q Q Q 的堆顶，会在后面被弹出，并不会影响答案。

Code：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct Building{
	int t1, t2;
	friend bool operator < (Building p1, Building p2){
		return p1.t2 < p2.t2; // 按照任务的截止时间排序
	}
}a[150005];

void solve()
{
	int n; cin >> n;
	for(int i = 1; i <= n; i ++) cin >> a[i].t1 >> a[i].t2;
	sort(a + 1, a + n + 1);
	
	ll cnt = 0, tim = 0; // cnt表示修好的个数，tim表示当前时间
	priority_queue <int> Q; // 默认大根堆。存储所有修过的花费的时间
	for(int i = 1; i <= n; i ++){
		tim += a[i].t1;
		cnt ++;
		Q.push(a[i].t1);
		if(tim > a[i].t2){ // 超时了，就把之前最浪费时间的那个报废掉（也可能这一轮的a[i]刚放进去就被报废了）
			cnt --;
			tim -= Q.top(); Q.pop();
		} 
	}
	cout << cnt << '\n';
}

signed main()
{
	ios :: sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	solve();
	return 0;
}

注意：因为 1 ≤ T 1 < T 2 < 2 31 1 \le T_1 < T_2 < 2^{31} 1≤T1​<T2​<231，稍微加一加就爆 int 了，要开long long！！！

补充：上面两个题都是比较简单的**“反悔堆”模型，还有更高级（也更难）的“反悔自动机”**模型。本人功力不足，建议大家上网查阅学习。

End

拓展延申：反悔贪心是OI竞赛中的一个重要知识点，会和不会的区分非常明显。一个很好的例子是，本文中两道题都是蓝题，但个人觉得其思维难度比某些绿题甚至黄题还低。

蒟蒻本人也在仔细研究。下面两篇文章写得特别详细特别好，建议大家阅读：

1. 详细总结反悔贪心各种模型及做法
2. 反悔贪心刷题指南+题解

洛谷大佬整理的反悔贪心题单：『进阶方法篇』反悔贪心系列

让我们一起学习进步吧！拜拜ヾ(•ω•`)o