程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> uva 669(貪心)

uva 669(貪心)

編輯:關於C++

題意:有連續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;
}


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved