[HAOI2011] problem a

题目描述

一次考试共有 $n$ 个人参加，可能出现多个人成绩相同的情况。第 $i$ 个人说：“有 $a_i$ 个人成绩比我高， $b_i$ 个人成绩比我低。”

请求出最少有几个人没有说真话。

对于 $100\%$ 的数据，保证 $1 \leq n \leq 10^5$ ， $0 \leq a_i, b_i \leq n$ 。

题解

一个人合法区间为 $[l_i=a_i+1,r_i=n-b_i]$ ，先把几个一定不可能的情况剔除，然后按 $r_i$ 排序，接着 DP，设 $f_i$ 表示到第 $i$ 个区间的最优解。

代码

const int N = 1e5 + 5;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n, firfakeN, secfakeN;

	struct node {
		int l, r, val;
	} a[N], fakeA[N];

	int f[N];

	bool comp1 (node a, node b) { return a.l == b.l? a.r < b.r: a.l < b.l; }
	bool comp2 (node a, node b) { return a.r == b.r? a.l < b.l: a.r < b.r; }

	int main () {
		firfakeN = Read();
		for (int i = 1; i <= firfakeN; i++) {
			int r = firfakeN - Read(), l = Read() + 1;
			if (l <= r) fakeA[++secfakeN] = (node) {l, r};
		}
		sort (fakeA + 1, fakeA + 1 + secfakeN, comp1);
		for (int i = 1; i <= secfakeN; i++) {
			if (i == 1 || fakeA[i].l != fakeA[i - 1].l || fakeA[i].r != fakeA[i - 1].r) {
				a[++n] = fakeA[i]; a[n].val = 1;
			} else if (a[n].val < a[n].r - a[n].l + 1) a[n].val++;
		}
		sort (a + 1, a + 1 + n, comp2);
		f[1] = a[1].val;

//		printf ("%d\n", secfakeN);

		for (int i = 2; i <= n; i++) {
			int l = 1, r = i - 1;
			while (l <= r) {
				int mid = l + r >> 1;
				if (a[mid].r < a[i].l) l = mid + 1;
				else r = mid - 1;
			}
			f[i] = max(f[i - 1], f[r] + a[i].val);
		}
		printf ("%d\n", firfakeN - f[n]);
		return 0;
	}
}

int main () {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	Main::main();
	return 0;
}