UVa 501 – Black Box

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=442

利用二分搜尋法尋找要插入Black Box的點，使Black Box非嚴格遞減排序。

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;

int main()
{
	int dataset;
	int M, N;
	int A[30001];
	int U[30001];
	int Box[30001];
	int size, index;

	scanf("%d", &dataset);
	while(dataset --)
	{
		scanf("%d %d", &M, &N);
		for(int i = 1; i <= M; i ++)
			scanf("%d", &A[i]);
		for(int i = 1; i <= N; i ++)
			scanf("%d", &U[i]);

		size = 0, index = 0;
		for(int i = 1; i <= N; i ++)
		{
			while(size < U[i])
			{
				size ++;
				int key = A[size];

				int l = 1, r = size - 1, m;
				while(l <= r)
				{
					m = (l + r) / 2;
					if(Box[m] < key)
						l = m + 1;
					else
						r = m - 1;
				}

				for(int i = size - 1; i >= l; i --)
					Box[i + 1] = Box[i];
				Box[l] = key;

			}

			index ++;
			printf("%d\n", Box[index]);
		}

		if(dataset > 0) printf("\n");
	}

	return 0;
}