uva 669(貪心)

uva 669(貪心)

題意：有連續n塊內存，然後有k個文件，每個文件可以分為ki塊放到內存裡，其他內存塊為空，現在給出每個文件的ki個碎片在內存中的放在第幾塊(碎片有序)，然後開始進行內存塊內容的移動，操作a b表示把內存a中的東西放到內存b中，前提是b為空，要求最少的操作使文件能夠按順序從最小的內存塊開始存儲，輸出順序操作過程。

題解：用一個flag[i] = j表示位置i上放的碎片應該放到位置j上，可以先遍歷一遍把能放碎片的先放，然後開始循環，挑出一個擺放不正確的位置，把碎片放到空閒位置，然後循環遍歷把能放到正確位置的碎片放到正確位置，直到全部都對。

#include 
#include 
const int N = 10005;
int n, k, flag[N], num;

bool judge() {
	for (int i = 1; i <= num; i++)
		if (flag[i] != i)
			return false;	
	return true;
}

void solve() {
	int c = 0;
	while(1) {
		int cc = c;
		for (int i = 1; i <= num; i++) {
			if (!flag[i]) {
				for (int j = 1; j <= n; j++)
					if (flag[j] == i) {
						c++;
						printf("%d %d\n", j, i);
						flag[i] = i;
						flag[j] = 0;
						break;
					}
			}
		}
		if(c == cc)
			break;
	}
}

int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		scanf("%d%d", &n, &k);
		memset(flag, 0, sizeof(flag));
		int	temp, a;
		num = 0;
		for (int i = 0; i < k; i++) {
			scanf("%d", &temp);
			for (int j = 0; j < temp; j++) {
				scanf("%d", &a);
				flag[a] = ++num;
			}
		}
		if (judge())
			printf("No optimization needed\n");
		else {
			solve();
			while (1) {
				for (int i = 1; i <= num; i++) {
					if (flag[i] && flag[i] != i) {
						for (int j = num + 1; j <= n; j++)
							if (!flag[j]) {
								printf("%d %d\n", i, j);
								flag[j] = flag[i];
								flag[i] = 0;
								break;
							}
						break;
					}
				}
				solve();
				if (judge())
					break;
			}
		}
		if (t)
			printf("\n");
	}
	return 0;
}