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

Re:提供思路! 和比较容易错的情况!自己写了个快排+贪心的!附代码!!!!(仅供参考)

Posted by hunt at 2011-03-06 15:20:52 on Problem 2376
In Reply To:提供思路! 和比较容易错的情况!自己写了个快排+贪心的!附代码!!!!(仅供参考) Posted by:2007210562 at 2009-08-11 21:06:44
#include <stdio.h>
#include <algorithm>
using namespace std;

struct cow_t{
    int s;
    int e;
}cow[255010];

int cmp(struct cow_t a, struct cow_t b)
{
    if(a.s == b.s) return a.e < b.e;
    return a.s < b.s;
}

int main()
{
    int n;
    int t;
    int i, j;
    int start, end;
    int cnt = 0;
    
    scanf("%d%d", &n, &t);
    for(i = 0; i < n; i++)
    {
        scanf("%d%d", &cow[i].s, &cow[i].e);   
    }

    sort(cow, cow+n, cmp);

    if(cow[0].s == 1)
    {
        j = 0;
        cnt = 1;
        start = end = cow[0].e;
        while(1)
        {
            for(i = j + 1; i < n; i++)
            {
                if(cow[i].s - 1 <= start && cow[i].e > end)
                {
                    end = cow[i].e;
                    j = i;
                }
            }
            if(end == start) break;
            cnt++;
            if(cow[j].e == t) break;
            start = end = cow[j].e;
        }
        if(cow[j].e == t) printf("%d\n", cnt);
        else printf("-1\n");
    }
    else
    {
        printf("-1\n");
    }

    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