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

贪心ac,附代码

Posted by liu125008 at 2017-03-06 12:08:03 on Problem 2376
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int N,T,ans;
struct c{int l,r;}cow[25005];
bool cmp(c a,c b){return a.l<b.l;}
int main()
{
    scanf("%d%d",&N,&T);
    for(int i=1;i<=N;i++)
        scanf("%d%d",&cow[i].l,&cow[i].r);
    sort(cow+1,cow+N+1,cmp);
    int l=0,i=0;//这里l处置为0
    while(l<T)
    {
        int maxr=-1,maxri;
        while(cow[++i].l<=l+1)//小于l+1而不是小于l
            maxr=cow[i].r>maxr?cow[maxri=i].r:maxr;
        if(maxr==-1){printf("-1");return 0;}//如果不能找到可以继续覆盖的牛就结束
        ans++;
        i--;//下次找牛从上次失败的地方开始
        l=maxr;//更新最右边界
    }
    printf("%d",ans);
    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