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