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 maqian7211396 at 2021-06-26 15:11:38 on Problem 2376
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;

typedef pair<int, int> PII;

bool cmp(PII &a, PII &b){
    if(a.first == b.first)
        return a.second > b.second;
    return a.first < b.first;
}

vector<PII> cows;
int n, t;
void solve(){
    sort(cows.begin(), cows.end(), cmp);
    // for(auto c : cows){
    //     cout << "a: " << c.first << "  b: " << c.second << endl;
    // }

    int ans = 0;
    int st = 0, ed = 0, j = 0;
    while( st < t){
        for (int i = j; i < n; i++)
            if(cows[i].first <= st + 1 && cows[i].second > ed){
                ed = cows[i].second;
                j = i;  // 优化下次搜索路径,不优化会超时
            }
        if(ed == st){
            ans = -1;
            break;
        }
        st = ed;
        ans++;
    }
    printf("%d\n", ans);
}

int main()
{
    scanf("%d%d", &n, &t);
    cows = vector<PII>(n);
    for (int i = 0; i < n; i++){
        int a, b;
        scanf("%d%d", &a, &b);
        cows[i] = PII(a, b);
    }
    solve();

    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