Codeforces Round #274 (Div. 2) C. Exams (贪心)

题意:给\(n\)场考试的时间,每场考试可以提前考,但是记录的是原来的考试时间,问你如何安排考试,使得考试的记录时间递增,并且最后一场考试的时间最早.
题解:因为要满足记录的考试时间递增,所以我们用结构体记录两个时间,并按第一个时间排序,然后遍历考试时间,\(ans\)记录上次考试的时间,我们每次将两个时间和\(ans\)比一下,如果提前考试的时间比\(ans\)小,说明我们一定不能提前考试(因为时间已经晚了),否则就提前考掉.

代码:

struct misaka{

    int a,b;

    bool operator < (const misaka &mikoto) const{

        if(a==mikoto.a) return b<mikoto.b;

        return a<mikoto.a;

    }

}e[N];

int n;

int main() {

    //ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    n=read();

    for(int i=1;i<=n;++i) e[i].a=read(),e[i].b=read();

    sort(e+1,e+1+n);

    int ans=0;

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

        if(e[i].b>=ans) ans=e[i].b;

        else ans=e[i].a;

    }

    printf("%d\n",ans);

    return 0;

}

巴特西

Codeforces Round #274 (Div. 2) C. Exams (贪心)

最新文章

热门文章