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;
}

这篇关于hdu4882-ZCC Loves Codefires（贪心）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---