首页 > ACM题库 > HDU-杭电 > hdu 2491 Priest John’s Busiest Day-贪心-[解题报告]C++
2014
01-26

hdu 2491 Priest John’s Busiest Day-贪心-[解题报告]C++

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?

Please note that:

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

题目大意:一个牧师要主持n个婚礼,牧师参加每个婚礼的时间要大于婚礼总时间的一半,给出每个婚礼的起止时间,问能否安排牧师主持每一个婚礼。

思路:贪心思想。按每个婚礼的中间时间(即牧师离开该婚礼的最早时间)升序排序。如果中间时间相等,按开始时间升序排序。然后依次安排即可。

#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;
}

解题转自:http://blog.csdn.net/crazy_xiaohe/article/details/8881950


  1. 要注意媒体集中效应,突然间一个事件引发一段时间内某一类事件的集中报道,然后给你一种假象。 有时候某些事情可能一直都有发生,通过媒体让你感觉变多了而已。

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

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

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

  5. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。