Oiclass PUJI 1353 题解

贪心 + 大模拟

题目简述

你是一名医生，是这家医院有且只有的一个医生。现在有 \(n\) 个患者要来手术，每个患者有四个属性：\(t\) 指患者到达医院的时间、\(a\) 指患者手术后会支付给你的钱、\(b\) 指患者所需的手术时间、\(p\) 是患者的严重程度，\(p\) 越小，患者就越严重。现在如果一个患者看到一个 \(p\) 值比他更大的患者正在手术，那么他就会很生气，你就会一分钱也得不到，因此你不希望这种情况发生。现在你需要在 \(k\) 的时间内处理一些患者，并使得你所得到的钱最多。注意，如果一个患者的手术还没有完成，你并不能处理其他患者。

思路

先对患者按照严重程度排序，越严重的越靠前。然后在 \(1 \sim k\) 的空闲时间中取出一段给这个患者。并将 \(1 \sim k\) 的时间分割成另外两端空闲时间（注意要剔除这位患者的治疗时间）。依此类推，使用一个平衡的红黑树维护这样的一个保存空闲时间的数据结构即可。注意细节非常多。

实现

这里使用 STL 容器 set 类维护空闲时间（set 就是一个十分平衡的红黑树）。先对病人排序，然后依次处理。注意一个细节，如果删除一个迭代器（set<T>::iterator）所指向的元素，那么这个迭代器将失效，无论你做什么操作，这个迭代器都将指向一个无效的内存。如果把这个迭代器比作指针的话，那么他现在就是一个野指针，我们需要尽可能的避免野指针的出现。毕竟谁也不想 segmentation fault 。其次就是加入元素，当你往 set 中插入元素时，这个迭代器将指向错误的元素，虽然不会 RE ，但是你也会喜提 WA 。这一点我是调了非常久的。然后就是可以用 set 自带的 lower_bound 函数实现元素的快速二分查找，进一步优化代码。

坑点讲完了之后，一点都不简单的实现一下就可以了：

#include <iostream>
#include <algorithm>
#include <set>

#define int long long

using namespace std;

struct patient {
	int p, t, a, b;
} a[100009];

inline bool cmp(patient a, patient b) {
	return a.p < b.p;
}

int n, k, ans;
set<pair<int, int> > s;

signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
	freopen("op.in", "rt", stdin);
	freopen("op.out", "wt", stdout);
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> a[i].p;
	}
	for (int i = 1; i <= n; i++) {
		cin >> a[i].t;
	}
	for (int i = 1; i <= n; i++) {
		cin >> a[i].a;
	}
	for (int i = 1; i <= n; i++) {
		cin >> a[i].b;
	}
	sort(a + 1, a + n + 1, cmp);
	s.emplace(1, k);
	for (int i = 1; i <= n; i++) {
		if (s.empty()) {
			break;
		}
		set<pair<int, int> >::iterator it = s.lower_bound({a[i].t, 0});
		set<pair<int, int> >::iterator it2 = it;
		if (it != s.begin()) {
			it2--;
		}
		if (it2 -> first <= a[i].t && a[i].t <= it2 -> second) {
			it = it2;
		} 
		if (it != s.end()) {
			a[i].t = max(a[i].t, it -> first);
			if (a[i].t <= it -> second) {
				if (a[i].t >= it -> first) {
					int l = it -> first, r = it -> second;
					s.erase(it);
					s.emplace(l, a[i].t - 1);
					s.emplace(a[i].t, r);
					it = s.lower_bound({a[i].t, 0});
				}
				vector<set<pair<int, int> >::iterator> v;
				while (it != s.end()) {
					int l = it -> first, r = it -> second;
					if (r - l + 1 >= a[i].b) {
						ans += a[i].a;
						s.erase(it);
						if (r - l + 1 > a[i].b) {
							s.emplace(l + a[i].b, r);
						}
	 					break;
					} else {
						v.push_back(it);
						it++;
					}
				}
				for (set<pair<int, int> >::iterator j : v) {
					s.erase(j);
				}
			}
		}
	}
	cout << ans;
}