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

sort + 贪心,直接附代码

Posted by 2510243467 at 2021-03-18 14:54:39 on Problem 2376
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

struct inter{
    int s, g;

    inter(int s = 0, int g = 0): s(s), g(g) {}
    bool operator < (const inter& b) const {
        if(this->s != b.s)
            return this->s < b.s;
        else
            return this->g < b.g;
    }
};
const int maxn = 25000+5;
const int INF = 1e8;
int N, T;
inter itv[maxn];

int tanxin()
{
    int ans = 0, g;
    int left = upper_bound(itv, itv+N, inter(1, INF)) - itv;
    int right;
    if(left == 0)
        return -1;
    else
    {
        left--;
        g = itv[left].g;
        ans++;
    }
    while(g < T)
    {
        right = upper_bound(itv+left, itv+N, inter(g+1, INF)) - itv;
        g = 0;
        int maxpos = -1;
        for(int i = left+1; i<right; i++)
        {
            if(itv[i].g > g)
            {
                maxpos = i;
                g = itv[i].g;
            }
        }
        if(maxpos == -1)
            return -1;
        else
        {
            left = maxpos;
            ans++;
        }
    }
    return ans;
}


int main()
{
    scanf("%d %d", &N, &T);
    for(int i = 0; i<N; i++)
        scanf("%d %d", &itv[i].s, &itv[i].g);
    sort(itv, itv+N);

    int ans = tanxin();
    printf("%d\n", 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