洛谷P1496 火烧赤壁【题解】

事先声明

本题解文字比较多，）。

题目简要

给定每个起火部分的)

最后一次浅浅谈一下

我们考虑把读进来的 ）自己思考，如果想不会请在评论区打出来，我会解答。

Code

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 2e4 + 7;

int n, a[2 * MAXN], b[2 * MAXN], rk[2 * MAXN], cf[2 * MAXN], cnt;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n;
	for (int i = 1; i <= n; i ++) 
		cin >> a[++ cnt], cin >> a[++ cnt];
	
	memcpy(b + 1, a + 1, 2 * n * sizeof(int));
	sort(b + 1, b + 1 + 2 * n);
	int k = unique(b + 1, b + 1 + 2 * n) - (b + 1);

	for (int i = 1; i <= 2 * n; i++) 
		rk[i] = lower_bound(b + 1, b + 1 + k, a[i]) - b;
	for (int i = 1; i <= 2 * n; i += 2) {
		int r =rk[i + 1], l = rk[i];
		cf[l] ++, cf[r] --;
	}
	int ans = 0, sum = 0;
	for (int i = 1; i <= k; i++) {
		sum += cf[i];
		if (sum > 0) ans += b[i + 1] - b[i];
	}
	cout << ans;
	return 扶苏咕咕咕~~~;
}

完结撒花✿✿ヽ(°▽°)ノ✿