Problem L - School Reunion —— 思维

本文主要是介绍Problem L - School Reunion —— 思维，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

So, the alumni association of your school is arranging it’s annual reunion tomorrow. N+1
people will attend the ceremony, which includes Mr. Kashem, a notable alumnus of the
school. But he can’t stay for a long period of time, because you know, he has other
important things to do. However, Mr. Kashem wants to meet at least P​ persons. His
assistant has acquired information about tomorrow’s plan of the N​ other persons - the
time they will arrive, and the time they will exit. Now he needs to figure out the minimum
amount of time Mr. Kashem has to stay on the reunion to meet at least P​ persons. It is
obviously complicated to solve this problem by hand, and Mr. Kashem’s assistant has zero
knowledge on programming. Can you help him solving this problem?
Input Specification
First line of input contains an integer T​, indicating the number of test cases. Each test case
starts with a line containing two integers N​ and P​. Here N​ indicates the number of people
other than Mr. Kashem, who will attend the reunion. And P​ indicates the minimum number
of people Mr. Kashem wants to meet. Following N​ lines contain two integers each, st​
i​ and
en​
i​
, denoting the entry and exit time of the i​
th​ person.
Constraints
1 ≤ T ≤ 30
1 ≤ P ≤ N ≤ 100000
1 ≤ sti ≤ eni ≤ 1000000000
Use fast input method. For example, prefer using scanf to cin in C/C++.
Output Specification
For each test case, print the case number starting from 1, followed by the answer to the
case in a separate line. See sample I/O for better understanding.
Statements
Online Selection Contest, BACS Regional Programming Camp, 2018
BACS High School Programming Contest, 2018
Input Output
2
5 3
1 3
8 12
6 9
14 17
2 7
3 3
1 6
4 7
6 9
Case 1: 1
Case 2: 0

题意：

给你n个线段，让你求出最短的长度使得这个长度能穿过至少p个线段

题解：

很容易就得出一个结论：这个长度必定是在某个线段的结尾之后或者开头之前包括这个结尾或者开头。
那么我们只要遍历每一个结尾和开头就能找出答案，我们只要把结尾和开头放到两个数组里，在找结尾的时候只需要找到第一个大于他的开头，再往下找就好了，但是注意有些线段是穿过这个结尾的，那么我们就要把那些线段数量给加上去，就是lower_bound结尾,upper_bound开头，再减一减就ok了，找开头只需要把所有数对2e9反一下就好了

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pill pair<int,int>
const int N=1e5+9;pill ed[N];
int st[N],en[N];int main()
{int t;cin>>t;int ca=0;while(t--){int p,n;scanf("%d%d",&n,&p);for(int i=1;i<=n;i++){scanf("%d%d",&ed[i].first,&ed[i].second);st[i]=ed[i].first;en[i]=ed[i].second;}if(p==1){printf("Case %d: 0\n",++ca);continue;}sort(st+1,st+1+n);sort(en+1,en+1+n);int ans=2e9;for(int i=1;i<=n;i++){int pos=lower_bound(st+1,st+1+n,ed[i].second)-st;int need=p-1+(ed[i].first==ed[i].second?1:0);need-=((n-(lower_bound(en+1,en+1+n,ed[i].second)-en)+1)-(n-(upper_bound(st+1,st+1+n,ed[i].second)-st)+1));if(ed[i].first!=ed[i].second)need++;if(need<=0){ans=0;break;}int idx=pos+need-1;if(idx>n)continue;ans=min(ans,st[idx]-ed[i].second);}for(int i=1;i<=n;i++)ed[i].first=2e9-ed[i].first,ed[i].second=2e9-ed[i].second,st[i]=2e9-st[i],en[i]=2e9-en[i];sort(st+1,st+1+n);sort(en+1,en+1+n);for(int i=1;i<=n;i++){int pos=lower_bound(st+1,st+1+n,ed[i].second)-st;int need=p-1+(ed[i].first==ed[i].second?1:0);need-=((n-(lower_bound(en+1,en+1+n,ed[i].second)-en)+1)-(n-(upper_bound(st+1,st+1+n,ed[i].second)-st)+1));if(ed[i].first!=ed[i].second)need++;if(need<=0){ans=0;break;}int idx=pos+need-1;if(idx>n)continue;ans=min(ans,st[idx]-ed[i].second);}printf("Case %d: %d\n",++ca,ans);}return 0;
}

这篇关于Problem L - School Reunion —— 思维的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---