题解

YangDavid 2020-08-03 15:34:58 2020-08-03 15:58:34

第一问,对每名学生,计算与其来馆时间交集非空的学生个数+1的值。这些值的最大值就是答案。

第二问,对每个时刻,计算有多少学生在馆,取最大值即为答案。

正确性请自行思考,代码见 AC 提交,时间复杂度

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 202020;
int n, pre[MAXN], suf[MAXN], cc[MAXN], ans1, ans2, l[MAXN], r[MAXN];
int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) {
		scanf("%d%d", &l[i], &r[i]);
		cc[l[i]]++, cc[r[i]]--;
		pre[r[i]]++, suf[l[i]]++;
	}
	for(int i = 1; i < MAXN; ++i) {
		cc[i] += cc[i - 1];
		pre[i] += pre[i - 1];
		ans2 = max(ans2, cc[i]);
	}
	for(int i = MAXN-2; i >= 0; --i)
		suf[i] += suf[i + 1];
	for(int i = 1; i <= n; ++i)
		ans1 = max(ans1, n - pre[l[i]] - suf[r[i]]);
	printf("%d %d\n", ans1, ans2);
	return 0;
}