| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
没人留言啊。。我留个题解把对于任意两个婚礼:
可以发现如果某个婚礼中间点小于另外一个婚礼中间点,则对于这个婚礼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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator