題目連結

https://zerojudge.tw/ShowProblem?problemid=a673

https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=967

參考文章

#UVa：10026－Shoemaker’s Problem - 翼世界夢想領域

本題要點

罰金越高的越先做，比較方式如下

如果「前一筆工作所需天數 * 當前工作罰金」大於「當前工作所需天數 * 前一筆工作罰金」

就將該筆工作往前排

因為罰金越高，先做了等於賺了這筆罰金（想法來自參考文章）

我用的方法可以通過，但效率不是很高…氣泡排序XD

還請版上大大們有更好的方法不吝賜教 ><！！

參考解答

解一：

n = int(input())

for case in range(n):
	space = input()
	day = int(input())
	data = []
	result = []
	for i in range(day):
		data.append(list(map(int, input().split())))
		result.append(i+1)

	# sort
	for i in range(day):
		for j in range(day-1, i, -1):
			if data[j][1] * data[j-1][0] > data[j][0] * data[j-1][1]:
				data[j-1], data[j] = data[j], data[j-1]
				result[j], result[j-1] = result[j-1], result[j]
			
	print(*result)
	if case < n-1:
		print()

回主頁