2014
01-26

# Priest John’s Busiest Day

John is the only priest in his town. October 26th is the John’s busiest day in a year because there is an old legend in the town that the couple who get married on that day will be forever blessed by the God of Love. This year N couples plan to get married on the blessed day. The i-th couple plan to hold their wedding from time Si to time Ti. According to the traditions in the town, there must be a special ceremony on which the couple stand before the priest and accept blessings. Moreover, this ceremony must be longer than half of the wedding time and can’t be interrupted. Could you tell John how to arrange his schedule so that he can hold all special ceremonies of all weddings?

John can not hold two ceremonies at the same time.
John can only join or leave the weddings at integral time.
John can show up at another ceremony immediately after he finishes the previous one.

The input consists of several test cases and ends with a line containing a zero.

In each test case, the first line contains a integer N ( 1 ≤ N ≤ 100,000) indicating the total number of the weddings.

In the next N lines, each line contains two integers Si and Ti. (0 <= Si < Ti <= 2147483647)

The input consists of several test cases and ends with a line containing a zero.

In each test case, the first line contains a integer N ( 1 ≤ N ≤ 100,000) indicating the total number of the weddings.

In the next N lines, each line contains two integers Si and Ti. (0 <= Si < Ti <= 2147483647)

3
1 5
2 4
3 6
2
1 5
4 6
0

NO
YES

http://acm.hdu.edu.cn/showproblem.php?pid=2491

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
struct node
{
int start,end,last,middle;
}wedding[100005];
int cmp(const void* a,const void* b)
{
if((*(node*)a).middle == (*(node*)b).middle)
return (*(node*)a).start-(*(node*)b).start;
else
return (*(node*)a).middle-(*(node*)b).middle;
}
int main()
{
int n,time,i;
while(scanf("%d",&n),n){
for(i=0;i<n;i++){
scanf("%d%d",&wedding[i].start,&wedding[i].end);
wedding[i].last=(wedding[i].end-wedding[i].start)/2+1;//仪式持续时间超过婚礼一半
wedding[i].middle=wedding[i].start+wedding[i].last;
}
qsort(wedding,n,sizeof(wedding[0]),cmp);
time=wedding[0].start;
for(i=0;i<n;i++){
if(time>wedding[i].end-wedding[i].last){
break;
}
if(time<=wedding[i].start)
time=wedding[i].middle;
else
time+=wedding[i].last;
}
if(i==n) printf("YES\n");
else printf("NO\n");
}
return 0;
}

1. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。

2. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮

3. 博主您好，这是一个内容十分优秀的博客，而且界面也非常漂亮。但是为什么博客的响应速度这么慢，虽然博客的主机在国外，但是我开启VPN还是经常响应很久，再者打开某些页面经常会出现数据库连接出错的提示