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 |
O(n*n) 复杂度就可AC#include <iostream> #include <fstream> #include <vector> #include <queue> #include <stack> #include <set> #include <map> #include <string> #include <sstream> #include <math.h> #include <string.h> #include <algorithm> #include <numeric> #include <deque> #include <climits> using namespace std; typedef long long ll; // const double M_PI = acos(-1.0); // const double E = 2.71828182845904523536029; int main() { int T; cin >> T; for (int t = 0; t < T; t++) { int n; cin >> n; vector<pair<int, int>> sticks; sticks.push_back(make_pair(0, 0)); for (int i = 0; i < n; i++) { int l, w; cin >> l >> w; sticks.push_back(make_pair(l, w)); } sort(sticks.begin(), sticks.end()); vector<bool> used(n+1); int ans = 0; used[0] = true; int last = 0; for (int i = 1; i <= n; i++) { if (used[i]) continue; ans++; used[i] = true; last = i; for (int j = i + 1; j <= n; j++) { if (used[j]) continue; if (sticks[j].first >= sticks[last].first && sticks[j].second >= sticks[last].second) { last = j; used[j] = true; } } } cout << ans << endl; } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator