Survey in Class

题面翻译

有 $n$ 个学生同时对课堂内容进行了预习。有 $m$ 个问题，第 $i$ 个人预习的问题是一个区间，可以用 $[l_i,r_i]$ 表示。每当老师问出一个问题，如果一个人不会，它的分数就会 $-1$，否则 $+1$。注意，分数可能为负。

现在你要问一些不重复的问题，最大化学生分数的极差，并输出这个值。

题目描述

Zinaida Viktorovna has $ n $ students in her history class. The homework for today included $ m $ topics, but the students had little time to prepare, so $ i $ -th student learned only topics from $ l_i $ to $ r_i $ inclusive.

At the beginning of the lesson, each student holds their hand at $ 0 $ . The teacher wants to ask some topics. It goes like this:

The teacher asks the topic $ k $ .
If the student has learned topic $ k $ , then he raises his hand by $ 1 $ , otherwise he lower it by $ 1 $ .

Each topic Zinaida Viktorovna can ask no more than one time.

Find the maximum difference of the heights of the highest and the lowest hand that can be in class after the survey.

Note that the student's hand can go below $ 0 $ .

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows.

The first line of each test case contains two integers $ n $ and $ m $ ( $ 2 \le n \le 10^5, 1 \le m \le 10^9 $ ) — the number of students and the number of topics, respectively.

Each of the next $ n $ lines of each test case contain two integers $ l_i $ and $ r_i $ ( $ 1 \le l_i \le r_i \le m $ ) — the endpoints of the segment of topics that $ i $ -th student has learned.

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ .

输出格式

For each test case, print one integer — the maximum difference of the heights of the highest and the lowest hand that can be in the class after the survey.

样例 #1

样例输入 #1

样例输出 #1

分析

为了差值最大化, 我们肯定要找一段自己有的, 这样子自己可以加分, 别人就要减分, 是最赚的

对于段与段之间的关系, 我们进行分类讨论

包含与被包含

很明显自己有的别人没有的部分 $=(r2-r1)+(l1-l2)=(r2-l2)-(r1-l1)$, 所以我们分别维护一个最大的还有最小的 $r-l$ 就可以了, 然后两个的差值就是这种情况的的最优答案

我们不用判断两段之间是否满足这种情况, 因为如果不满足我们在另一种情况讨论, 结果肯定会比这个计算结果要优, 我们取最大值的时候就会自动排除不符合的情况的
相交或者分离

对于这种情况, 如果是相交, 那么自己有别人没有的就是右边突出来的一段 $=r1-r2$, 如果是相离, 那就是 $r1-l1+1$, 为了是这一部分最长, 我们找到最小的那个 $r$ 即可, 让别的 $r$ 来减去即可

不要忘记考虑左边也会突出来一段, 与讨论右边段类似, 我们找到最大的 $l$ 让他减去其他的 $l$ 即可, 当然也要考虑相离的情况

和计算"包含"一样, 对所有的数求, 不判断是否满足这个关系, 因为如果是包含, 以这种计算方式计算出来的结果不会优于"包含"计算结果, 不会对答案产生影响

然后对于这两种分类求出来的最大值再合在一起求个最大值即可, 主要的切入点在这个分类讨论上, 没有用到什么很高级的算法

所以就算是难度系数比我目前的高, 也不一定就会用到很高级的算法, 还是思维上的难度

!: 还是那句话, 到了 10⁹, 开long long

代码

#include <iostream>
#include <algorithm>
const int N = 1e5 + 10;
using namespace std;
typedef long long ll;
struct A
{
	ll l, r;
}a[N];
int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	int t; cin >> t;
	while(t--)
	{
		ll ans = 0;
		ll n, m; cin >> n >> m;
		ll minr = 1e9, maxl = -1e9; 
		for(int i = 0; i < n; i++)
		{
			cin >> a[i].l >> a[i].r;
			minr = min(minr, a[i].r), maxl = max(maxl, a[i].l);
		}
		//包含
		ll maxn = -1e9, minn = 1e9;
		for(int i = 0; i < n; i ++)
		{
			maxn = max(maxn, a[i].r - a[i].l);
			minn = min(minn, a[i].r - a[i].l);
		}
		ans = maxn - minn;
		//右边突出来 
		for(int i = 0; i < n; i ++)
		{
			if(a[i].l > minr) ans = max(ans, a[i].r - a[i].l + 1);
			else ans = max(ans, a[i].r - minr);
		}
		//左边突出来
		for(int i = 0; i < n; i ++)
		{
			if(a[i].r < maxl) ans = max(ans, a[i].r - a[i].l + 1);
			else ans = max(ans, maxl - a[i].l);
		}
		cout << ans * 2 << endl; 	//自己有别人没有, 自己加1别人就要减1, 所以要这一段的值要乘2
	}
}

JZTXT

CF1834D