贪心

区间问题

• 思路：如何确定根据左or右端点排序？
  -若为确定“最少点”或覆盖“最多区间”，则按右端点排序，结束时间越早，下一个越早进入
  -若为“覆盖区间”或“区间分组”，则按左端点排序，做到不重不漏

区间选点

• 注意点的范围，初始ed要设为负无穷，不能无脑设为0

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
struct Range
{
	int l, r;
	bool operator<(const Range& w) {
		return r < w.r;
	}
}ranges[N];

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> ranges[i].l >> ranges[i].r;
	}

	sort(ranges, ranges + n);

	// 初始化ed为负无穷
    int cnt = 0, ed = -2e9;

	for (int i = 0; i < n; i++) {
        // 新区间的左端点在ed之外，故要选新点，并更新cnt 和 ed
		if (ed < ranges[i].l) {
			cnt++;
			ed = ranges[i].r;
		}
	}

	cout << cnt << endl;

	return 0;
}

最大不相交区间数

• 思路：跟区间选点类似，按左端点排序，新区间左端点在当前ed右侧则cnt ++ 并更新ed

区间分组

• 思路：用小根堆存放各组的右端点，新区间的左端点若比最早结束的组还靠左，则不可能不相交，需要开新组，
  否则更新该组(将旧右端点pop，将新端点push)

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

const int N = 100010;

int n;
struct Range
{
	int l, r;
    // 区间分组，谁先来谁先分配组。故按左端点排序
	bool operator<(const Range& w) {
		return l < w.l;
	}
}r[N];

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) cin >> r[i].l >> r[i].r;

	sort(r, r + n);

	priority_queue<int, vector<int>, greater<int>> heap;

	for (int i = 0; i < n; i++) {
        // 没有组或者新区间跟所有组冲突，则开新组
		if (!heap.size() || r[i].l <= heap.top()) {
			heap.push(r[i].r);
		}
		else {
			// 否则，更新原来所在组的结束时间
			heap.pop();
			heap.push(r[i].r);
		}
	}

	cout << heap.size() << endl;

	return 0;
}

哈夫曼树

合并果子

• 思路： 用堆来存贮，每次取出最小的两堆合并，新堆是两堆之和，代价加上两堆之和

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

int main() {
	int n;
	cin >> n;

	priority_queue<int, vector<int>, greater<int>> heap;
	while (n--) {
		int x;
		cin >> x;
		heap.push(x);
	}

	int res = 0;
	while (heap.size() > 1) {
		// 取出来后不要忘了 pop
		int b = heap.top(); heap.pop();
		int a = heap.top(); heap.pop();
		// res += a + b ， 代价要累加
		res += a + b;
		heap.push(a + b);
	}

	cout << res << endl;

	return 0;
}

排序不等式

排队打水

• 思路： 用时短的排队时间长

绝对值不等式

• 思路： 到各点(一维)距离最短为中点(下标的 即 n >> 1, 对奇偶情况都适用)

推公式

• 思路： 类似国王游戏，考察两个对象，交换顺序后假定大小关系，从而得出排序依据

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 50010;

int n;
pair<LL, LL> cow[N];

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		LL w, s;
		cin >> w >> s;
		cow[i] = { w + s,s };
	}

	sort(cow, cow + n);

	LL res = -2e9, sum = 0;
	for (int i = 0; i < n; i++) {
		int w = cow[i].first - cow[i].second, s = cow[i].second;
		res = max(res, sum - s);
		sum += w;
	}

	cout << res << endl;

	return 0;
}