| ||||||||||
| 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