UVA1420 Priest John‘s Busiest Day 题解

题目： Priest John’s Busiest Day

在这里给出一个跟先前题解不一样的判断思路：

因为司仪要主持尽量多的婚礼，所以应将最晚开始时间小的婚礼先主持，最晚开始时间大的婚礼后主持。而前一场婚礼的主持又可能占用到下一场婚礼的时间，所以为了给前一场婚礼的主持留出时间，每场婚礼应该尽可能地晚主持。

用 sort 将结构体由开始时间从小到大的顺序排序一遍。然后，就一个个判断每场婚礼能否按时主持。i 从 2 开始枚举，如果前一场婚礼的开始时间，加上前一场婚礼的主持所用时间超过了后一场婚礼的最晚开始时间，就说明后一场场婚礼不能主持完了，直接输出 $‘NO‘$，反之则最后输出 $‘YES‘$。

完整代码：

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){
    if(ch=='-') w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;
}//快读
struct node{
    int begin,end,zw,half;//zw是最晚开始时间，half是主持所用时间
}a[100001];
bool cmp(node a,node b){
    return a.zw<b.zw;
}
int main() 
{
    int n;while(1){
    bool flag=1;n=read();if(n==0) return 0;//读到0就结束for(int i=1;i<=n;i++){
    a[i].begin=read(),a[i].end=read();a[i].half=(a[i].end-a[i].begin)/2+1;a[i].zw=a[i].end-a[i].half;//cout<<a[i].half<<" "<<a[i].zw<<endl;//调试代码}sort(a+1,a+1+n,cmp);for(int i=2;i<=n;i++){
    if(a[i-1].begin+a[i-1].half>a[i].zw){
    flag=0;cout<<"NO"<<endl;break;}}if(flag) cout<<"YES"<<endl;}return 0;
}

后记： 本蒟蒻的思路或代码如有问题还请各位 dalao 指出，感谢观看！