UVa 501 Black Box

想法：
    原本是用multiset來存每個數字，因為multiset為紅黑樹，想說從第一個元素iterate i次來GET第i個數字，但一個一個iterate效率太慢就TLE了。
    後來改用vector來存數字，每新增一個數字，就用binary search找到它該放的位置，然後用vector的insert來插入該數字，要GET第i個元素因為是vector就可以直接存取了，效率還不錯，UVa花了0.495秒。

	#include <cstdio>
	#include <vector>
	#include <algorithm>
	using namespace std;
	int A[30010];
	int main()
	{
	// freopen("input.txt","rt",stdin);
	int Case, M, N, tmp;
	scanf("%d", &Case);
	while (Case--) {
	scanf("%d %d", &M, &N);
	for (int i = 0; i < M; ++i)
	scanf("%d", &A[i]);
	vector<int> Box;
	int U, a = 0, i = 0; // a is index of A
	while (N--) {
	scanf("%d", &U);
	while (a < U) { // lower_bound回傳一個iterator指向Box裡面第一個>=A[a]的元素
	auto iter = lower_bound(Box.begin(), Box.end(), A[a]);
	Box.insert(iter, A[a++]);
	}
	printf("%d\n", Box[i++]);
	}
	if (Case) printf("\n");
	}
	return 0;
	}

view raw [UVa] 501-2 Black Box.cpp hosted with ❤ by GitHub

這是用set的版本：

	#include <cstdio>
	#include <set>
	using namespace std;
	int Case, M, N;
	int A[30010], U[30010];
	int main()
	{
	freopen("input.txt","rt",stdin);
	scanf("%d", &Case);
	while (Case--) {
	scanf("%d %d", &M, &N);
	for (int i = 0; i < M; ++i)
	scanf("%d", &A[i]);
	for (int i = 0; i < N; ++i)
	scanf("%d", &U[i]);
	multiset<int> Box;
	for (int i = 0, u = 0, a = 0; u < N; ++u, ++i)
	{
	while (a < U[u] && a < N)
	Box.insert(A[a++]);
	auto iter = Box.cbegin();
	for (int j = 0; j < i; ++j)
	++iter;
	printf("%d\n", *iter);
	}
	if (Case) printf("\n");
	}
	return 0;
	}

view raw [UVa] 501-1 Black Box.cpp hosted with ❤ by GitHub