Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

没人留言啊。。我留个题解把

Posted by lzqxh at 2011-11-13 18:04:32 on Problem 3927
对于任意两个婚礼:
可以发现如果某个婚礼中间点小于另外一个婚礼中间点,则对于这个婚礼MS一定要先主持。。为什么自己画图去。。。
如果婚礼中间点相等则
1.若婚礼长度是奇数:无解
2.若婚礼长度是偶数,且相等个数超过2个,无解
3.若婚礼长度是偶数,且相等个数等于2个,如:
1111 :则不是1120 就是 0211
 22

基于以上,结论可以推出正解就是贪心!,按中点排序,然后每个婚礼尽量早主持完(因为后面的婚礼一定会在它主持完再开始主持,所以它先搞定必定是最优到),如果发现婚礼中间点相等,且长度是偶数,则贪心判断能不能先主持完长的,不能就先主持短的

CODE:
//By Lin
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 100010

using namespace std; 

struct	Line{
	int x ,y,k,mid,l; 
}lines[maxn]; 

int	n; 

bool cmp(Line a , Line b )
{
	if ( a.mid != b.mid ) return a.mid < b.mid; 
	if ( a.k != b.k ) a.k > b.k; 
	return a.l > b.l;
}
bool	pan(int x ,int y )
{
	if ( lines[x].k == lines[y].k && lines[x].mid == lines[y].mid ) return true; 
	return false; 
}
int main()
{
	while ( scanf("%d" ,&n) != EOF )
	{
		if ( n == 0 ) break; 
		for (int i = 0; i<n; i++)
		{
			scanf("%d%d",&lines[i].x , &lines[i].y ); 
			int l = lines[i].y - lines[i].x;  
			lines[i].k = (l+1)%2; 
			lines[i].mid = lines[i].x + l/2; 
			lines[i].l = l/2; 
		}
		sort( lines , lines+n , cmp ); 
		bool f = true; 
		for (int i = 0; i<n-1; i++)
		{
			if ( lines[i].k == 1 && pan(i,i+1) ) { f = false; break; }
			if ( i<n-2 && pan(i,i+1) && pan(i+1,i+2) ) { f = false; break; }
		}

		if ( f ) 
		{
			int now = 0; 	
			for (int i = 0; i<n; i++)
			{
				if ( i<n-1 && pan(i,i+1) )
				{
					if ( lines[i].x > now ) now = lines[i+1].y; 
					else if ( lines[i+1].x > now ) now = lines[i].y; 
					else { f = false; break; }
				}
				else 
				{
					int st = max(now+1,lines[i].x);
					int ed = st + lines[i].l; 
					if ( ed > lines[i].y ) { f = false; break; }
					now = ed; 
				}
			}
		}
		if ( f ) printf("YES\n" ); 
		else printf("NO\n"); 
	}
	return 0; 
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator