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