本文主要是介绍SYZOJ 480【WQH大佬的逃♂离】 的题解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
这道题是我在英语课的时候感觉无聊,而又看到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
1
3 8
1 8
2 4
5 7
output
1 3
样例解释
图中红色曲线部分为选中的人,直线上红色区域为空闲时间。
input
4
10 23
4 15
16 19
15 18
18 18
7 11
20 22
20 21
23 23
14 21
7 85 35
32 32
5 25
27 32
7 27
15 2010 45
2 15
38 42
15 42
32 41
26 35
42 45
14 43
6 33
13 14
19 456 38
32 35
23 38
21 30
6 26
6 28
24 38
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 1000005int 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");elsecout<<ansNum<<" "<<ansT<<endl; ansNum=0;ansT=0;memset(b,0,sizeof(b));}return 0;
}
写在后面:
这是本蒟蒻第一次出题,出不了太高妙的题。
自己出数据的时候经历了很多磨♂难,明白了出数据也是充满艰辛的!
不过自己出题还真是挺有趣♂的。
挺难忘的一次经历!
这篇关于SYZOJ 480【WQH大佬的逃♂离】 的题解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!