hdu4882-ZCC Loves Codefires（貪心）

hdu4882-ZCC Loves Codefires（貪心）

題目：hdu4882-ZCC Loves Codefires

題目大意：給出n個問題，每個問題有兩個參數，一個ei（所要耗費的時間），一個ki（能得到的score）。每道problem需要耗費：（當前耗費的時間）*ki，問怎樣組合問題的處理順序可以使得耗費達到最少。

解題思路： e1 e2

k1 1 2

k2 3 4

這樣的兩道問題的組合方式有兩種：12組合

費用： 1 * 3 + （1 + 2） * 4 = 1 * 3 + 2 *4 + 1 * 4

21組合

費用： 2 * 4 + （ 2 + 1） * 3 = 1 * 3 + 2 * 4 + 2 * 3

可見這兩種組合就差在 是1 * 4 還是 2 * 3，所以只要將這些問題按照相鄰的兩個數ei和ki對應交叉相乘結果小的放前排序，最後累加起來就是要求的費用。

代碼：

#include 
#include 
#include 
using namespace std;

const int N = 1e5+5;
typedef _int64 ll;

struct ST{

 	ll ei, ki;
}st[N];

bool cmp (const ST &a, const ST &b) {

	return a.ei * b.ki < a.ki * b.ei;
}

int main () {
	
	int n;
	ll sum, temp;
	while (scanf ("%d", &n) == 1 && n) {
		
		for (int i = 0; i < n; i++) 
			scanf ("%I64d", &st[i].ei);
		for (int i = 0; i < n; i++)
			scanf ("%I64d", &st[i].ki);
		
		sort (st, st + n, cmp);
		
		sum = temp = 0;
		for (int i = 0; i < n; i++) {

			temp += st[i].ei;
			sum += temp * st[i].ki;
		}
		printf ("%I64d\n", sum);	
	}
	return 0;
}