Luogu P3553[POI2013]INS-Inspecotr

发表于 | 更新于 | 阅读次数：

分析

先二分答案转化成一个判定性问题，这样记录就没有先后之分了。

然后考虑什么情况会出现矛盾

  1. 两条记录是同一时刻的，但人数不同。

解决：直接特判

  1. 举个例子

小$A$在$x$时刻写过一个记录，又在$y$时刻写了一个记录，小$B$写除了他没有人了。

解决：对每个人记录一下最晚开始时间和最早结束时间当成一条线段，对于每个时间节点，算被几条线段覆盖，线段条数大于当前时间记录的人数时就是无解。

  1. 根据记录构造出一种方案，但是会超过n个人的限制的方案

解决：计算出他的最小符合条件的人数，判断是否$<=n$。

code:

点击显示代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<cstdio>
#define N 100010
#define inf 0x3f3f3f3f
int n, m, t[N], u[N], v[N], mn[N], mx[N], tot[N], st[N], en[N];
inline int read() {
	register int x = 0; register char ch = getchar();
	for (; ch < '0' || ch > '9'; ch = getchar());
	for (; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
	return x;
}
inline void write(int num) {
	if (num > 9)
		write(num / 10);
	putchar(num % 10 ^ 48);
}
template<class type>
type max(type &a, type &b) {
	return a > b ? a : b;
}
template<class type>
type min(type &a, type &b) {
	return a < b ? a : b;
}
bool check(int M) {
	for (int i = 1; i <= n; i++)
		mn[i] = inf, mx[i] = -inf;
	for (int i = 1; i <= m; i++)
		tot[i] = st[i] = en[i] = 0;
	for (int i = 1; i <= M; i++) {
		mn[u[i]] = min(mn[u[i]], t[i]), mx[u[i]] = max(mx[u[i]], t[i]);
		if (tot[t[i]] and tot[t[i]] != v[i] + 1)
			return false;
		tot[t[i]] = v[i] + 1;
	}
	for (int i = 1; i <= n; i++)
		if (mx[i] != -inf)
			st[mn[i]]++, en[mx[i]]++;
	int total = 0, now = 0, done = 0, notr = 0;
	for (int i = 1; i <= m; i++)
		if (tot[i]) {
			now += st[i];
			if (now > tot[i])
				return false;
			if (st[i] <= notr)
				notr -= st[i];
			else
				total += st[i] - notr, notr = 0;
			if (now + notr + done < tot[i])
				total += tot[i] - now - notr - done, notr = tot[i] - now - done;
			else {
				if (now + notr > tot[i])
					notr = tot[i] - now, done = 0;
				else
					done = tot[i] - now - notr;
			}
			now -= en[i]; done += en[i];
		}
	if (total > n)
		return false;
	return true;
}
int main() {
	int T;
	T = read();
	while (T--) {
		n = read(), m = read();
		for (int i = 1; i <= m; i++)
			t[i] = read(), u[i] = read(), v[i] = read();
		int l = 1, r = m + 1, mid;
		while (l < r) {
			mid = (l + r) >> 1;
			if (check(mid))
				l = mid + 1;
			else
				r = mid;
		}
		write(l - 1), putchar('\n');
	}
	return 0;
}