题意简介

有一个司仪，要主持n场婚礼，给出婚礼的起始时间和终止时间，每个婚礼需要超过一半的时间做为仪式，并且仪式不能终止。问说司仪能否主持n场婚礼。

输入格式

多组数据，每组数据输入一个\(N\)（\(N\)<=100000），接下来N行，每行输入\(Si\)，\(Ti\)两个数，当输入\(n=0\)时输入结束

输出格式

每行对应每组数据，用"YES"或"NO"代表能否主持完n场婚礼

算法分析

一眼贪心，要求主持完全部婚礼，每个婚礼主持时间为 \((Ti-Si)/2+1\) 因为时间必须超过一半，所以要加一

然后按照每个婚礼结束时间排序，贪心策略优先选择越早结束的婚礼解决，留时间解决后面的婚礼，然后Judge判断一下就可以了

代码

#include<bits/stdc++.h>

#define re register

#define ll long long

using namespace std;

inline int read()

{

	int k=1,sum=0;

	char c=getchar();

	for(;c<'0' || c>'9';c=getchar()) if(c=='-') k=-1;

	for(;c>='0' && c<='9';c=getchar()) sum=sum*10+c-'0';

	return sum*k;

}

const int N=1e5+10;

int n;

struct Task{

	int s,t,d;

}a[N];

inline bool cmp(Task x,Task y){

	return x.s+x.d<y.s+y.d;

}

inline bool Judge(){

	int cnt=0;

	for(re int i=1;i<=n;++i) {

		cnt=max(cnt,a[i].s)+a[i].d;

		if(cnt>a[i].t) return 0;

	}

	return 1;

}

int main()

{

	while(scanf("%d",&n)==1 && n>0) {

		for(re int i=1;i<=n;++i) {

			a[i].s=read(),a[i].t=read();

			a[i].d=((a[i].t-a[i].s)>>1)+1;

		}

		sort(a+1,a+n+1,cmp);

		cout<<((Judge()==1?"YES":"NO"))<<endl;

	}

	return 0;

}

/*

3

1 5

2 4

3 6

2

1 5

4 6

0

*/

巴特西

UVA1420 Priest John's Busiest Day【贪心】

题意简介

输入格式

输出格式

算法分析

代码

最新文章

热门文章