hdu 2491 贪心

#include<stdio.h>

#include<stdlib.h>

#define N 110000

struct node {

int u,v,len,time;

}ma[N];

int cmp(const void *a,const void *b){

return (*(struct node *)a).time-(*(struct node *)b).time;

}

int main() {

     int n,i,k;

     while(scanf("%d",&n),n) {

        for(i=0;i<n;i++) {

            scanf("%d%d",&ma[i].u,&ma[i].v);

            ma[i].len=(ma[i].v-ma[i].u)/2+1;//记录仪式进行的时间长度

            ma[i].time=ma[i].u+ma[i].len;//从第一次仪式开始到结束时间的长度

        }

        qsort(ma,n,sizeof(ma[0]),cmp);

        k=ma[0].time;//初始化为仪式的结束时间

        for(i=1;i<n;i++) {

            if(ma[i].v-ma[i].len<k)//如果当前的仪式的结束-其长度《上一次的结束世间直接退出

                break;

            if(k>ma[i].u)//如果上一次的结束时间高于本次的结束时间，就加上其长度

                k+=ma[i].len;

            else

                k=ma[i].time;//否则就等于本次的结束时间

        }

        if(i==n)

            printf("YES\n");

        else

            printf("NO\n");

     }

return 0;

}
巴特西

hdu 2491 贪心

最新文章

热门文章
