SYZOJ 480 WQH大佬的逃离题解

ACM-ICPC

Publish Date: 2018-09-27

这道题是我在英语课的时候感觉无聊，而又看到WQH大佬，于是突发灵感，想出了这道水题。

题目描述

众所周知，WQH大佬非常NB，所以经常有很多人来找WQH大佬问问题或者Van♂游戏。

但是WQH不能在别人身上花太多时间，因为他还有一个【数据删除】，WQH每天需要抽一些时间陪【数据删除】van♂游戏。

WQH每天有t个单位时间，而每天都有n个人来找WQH大佬，第i个人会在l[i],r[i]的单位时间段内围在WQH大佬身边，假如在某个时间段WQH大佬身边没有人，他就可以陪【数据删除】van♂游戏。但是因为来找WQH大佬的人实在是太多了，所以WQH决定找一个“性♂运”学生，让这个“性♂运”学生改天再来，从而让自己有更多的时间来陪【数据删除】van♂游戏。

但是WQH大佬和【数据删除】van♂的太多了，所以WQH大佬感到一丝虚♂弱，所以就来找你帮忙，将哪一个学生作为“性♂运”学生可以让WQH大佬陪【数据删除】的时间最多。如果无解，则输出 ”and*kgou“。无解情况指无论让哪个学生作为性♂运学生，都不能使WQH大佬陪【数据删除】van♂的时间更多.

~~WQH大佬：“你有毒吧？”。~~

本蒟蒻第一次出题，真·原创题，可能比较水，数据也是随机数。如果有错误，欢迎指正！
感谢@door♂阳提供的5组毒瘤数据（你们T掉的点都是他出的！）和样例解释！

输入格式

第一行一个整数T，表示有T组数据

接下来的T组测试数据：

第一行有2个整数n,t，用空格隔开，分别表示有多少个人来找WQH大佬，而WQH大佬有t各单位时间。

接下来n行，每行2个整数l，r，用空格隔开，分别表示第i个人在l，r单位时间段会在WQH大佬身边。

友情提示:最好~~(必须)~~加一个快读

输出格式
T行。

两个整数分别代表 “性♂运”学生的编号和把那个学生作为“性♂运”学生可以获得陪【数据删除】van♂游戏的时间。

如果无解，则输出 ”and*kgou“

(因为Andy真的可gou)

样例：

input

output

1 3

样例解释

图中红色曲线部分为选中的人，直线上红色区域为空闲时间。

input

output

1 6
3 5
1 4
and*kgou

说明：

对于20%的数据 n<=100,t<=1000

对于40%的数据 n<=10000,t<=100000

对于100%的数据 n<=5000000,t<=5000000,T<=10;

思路：

经过一番摸♂索，便会发现，要找到的那个学生只要是独自占有时间最长就好了，因为把这个学生赶走后，他独自占有的时间就回变成WQH大佬的空闲时间。所以只需求出来这个学生是谁就可以了！如果每个学生都没有独自占有时间，那就是无解啦！（即每个时间段都被覆盖了两次！）

做法：

用差分数组求出每个时间段的人数。
再用前缀和求出每个时间段只被一个人占用的时间是多少。
最后枚举每个人的占用时间段，看谁独自占用时间最多就是它啦!
如果没有人有独自占用时间，那就是无解啦！

代码很简单：

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

int n,t,T;
long long sum[maxn],l[maxn],r[maxn];
long long a[maxn],b[maxn],ansNum,ansT;

int main()
{
//	freopen("test11.out","w",stdout);
//	freopen("test11.in","r",stdin);
	cin>>T;
	while(T--){
		scanf("%d%d",&n,&t);
		for(int i=1;i<=n;i++){
			cin>>l[i]>>r[i];
			b[l[i]]++;b[r[i]]--;	
		}
		for(int i=1;i<=t;i++) a[i]=a[i-1]+b[i];
		for(int i=1;i<=t;i++) if(a[i] > 1) a[i]=0;
		for(int i=1;i<=t;i++) sum[i]=sum[i-1]+a[i];
		for(int i=1;i<=n;i++)
			if(sum[r[i]-1]-sum[l[i]-1] > ansT){
				ansT=sum[r[i]-1]-sum[l[i]-1];
				ansNum=i;
			}
		if(ansNum==0 && ansT==0)
			printf("and*kgou\n");
		else
			cout<<ansNum<<" "<<ansT<<endl;		
		ansNum=0;ansT=0;
		memset(b,0,sizeof(b));
	}
	return 0;
}