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

O(n*n) 复杂度就可AC

Posted by houzhe at 2022-01-10 07:49:42 on Problem 1065
#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:
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