首页 > 代码库 > 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 <stdio.h>
#include <stdlib.h>
#include <algorithm>
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;
}