| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
sort+区间贪心#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator