挑战程序竞赛系列（8）：2.1一往直前！贪心法（其他）
挑战程序竞赛系列（8）：2.1一往直前！贪心法（其他）
版权声明：本文为博主原创文章，未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434781
挑战程序竞赛系列（8）：2.1一往直前！贪心法（其他）
详细代码可以fork下Github上leetcode项目，不定期更新。
练习题如下：
- POJ 2393: Yogurt Factory
- POJ 1017: Packets
- POJ 3040: Allowance
- POJ 1862: Stripies
- POJ 3262: Protecting the Flowers
POJ 2393: Yogurt Factory
思路：
把存储成本转换成价格，做个比较即可。
200 400 300 500
88 89 97 91
a. 88 93 98 103 表示第一周生产全部酸奶的成本，已考虑存储成本
b. 89 94 99 表示第二周生产后续酸奶的成本，已考虑存储成本
c. 97 102 表示第三周生产后续酸奶的陈本，已考虑存储成本
所以，在这些所有可能的候选项中，每周都选取最小的成本进行生产即可。
贪心策略：
每周选择min(前周成本+S，本周成本) 代码如下：
public class SolutionDay24_P2393 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int S = in.nextInt();
int[] C = new int[N];
int[] Y = new int[N];
for (int i = 0; i < N; i++){
C[i] = in.nextInt();
Y[i] = in.nextInt();
}
System.out.println(solve(C, Y, S));
in.close();
}
private static long solve(int[] C, int[] Y, int S){
int minCost = 1 << 30;
long total = 0;
for (int i = 0; i < C.length; i++){
minCost = Math.min(minCost + S, C[i]);
total += minCost * Y[i];
}
return total;
}
}注意溢出，否则WA。
POJ 1017: Packets
有 1 * 1 到 6 * 6 的产品，最少用几个 6 * 6 的箱子装它们。
这道题总共就需要考虑六种情况：
- 产品为 6*6，直接打包，无多余空间
- 产品为 5*5，直接打包，有多余空间，留给 1 *1产品
- 产品为 4*4，直接打包，有多余空间，留给 1*1 ，2*2产品
- 产品为 3*3，特殊
- 产品为 2*2，特殊
- 产品为 1*1，特殊
首先一定是从 size比较大的产品考虑，因为它们剩余的空间可以多装一些size较小的物品，如果把size小的物品都包裹了，那么打包size大的物品必然会剩下很多空间，显然浪费了。
代码思路：
先打包size为6，5，4，3 的产品，产品3比较特殊，但总共就出现四种情况，所以可以用space来记录打包3时余下的size为2的个数。
这样，就能计算size为2可装的总个数，接着把所有的size为2的产品放入这些空间中，如果不够放，就开辟新的空间，来存放size为2的产品。
最后，计算产品1的剩余空间，存放，多出来的开辟新空间。
代码如下：
public class SolutionDay34_P1017 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (true){
int[] h = new int[6];
boolean isOver = true;
for (int i = 0; i < 6; i++){
h[i] = in.nextInt();
if (h[i] != 0) isOver = false;
}
if (isOver) break;
System.out.println(solve(h));
}
in.close();
}
static int[] space = {0,5,3,1};
private static int solve(int[] h){
int n = h[5] + h[4] + h[3] + (int)Math.ceil(h[2] / 4.0);
//计算能够放入2*2的个数
int y = 5 * h[3] + space[h[2] % 4];
if (h[1] > y){
n += Math.ceil((h[1] - y) / 9.0); //多出来的2*2块，每9个能拼成 6*6块
}
//计算能够放入1*1的个数
int x = 36 * n - 36 * h[5] - 25 * h[4] - 16 * h[3] - 9 * h[2] - 4 * h[1];
if (h[0] > x) {
n += Math.ceil((h[0] - x) / 36.0);
}
return n;
}
}POJ 3040: Allowance
这道题有些细节还没搞明白，但多少能发掘一点东西。可以简单分为三个阶段：
- 第一阶段，筛选那些面额比周工资大的那些coin，直接发放掉。
- 第二阶段，比较复杂。。。
该问题要转换一下，它的意思是说，尽可能多的给老牛发工资，所以我们可以这样理解：
求得所有面额的总工资，如在测试用例中，总工资为 10 * 1 + 1 * 100 + 5 * 120 = 710元，所以理想状态下，这些工资最多能够发 710 / 6 = 118 周。
但为什么是理想状态呢？因为该问题面值是不能被撕开的，所以如果（5+1）元被发完了，只能发（5+5）和（10）元的面额了，那么自然能发的周数减小了。
所以说该问题可以被看成：
尽可能的让面额组合接近C，此时能发的周数一定是最多的。那么问题来了，该怎么组合？
来证明一下：
因为我们知道，面额大于C的，与小的组合只会产生更大的面额，没必要，所以直接发放掉即可。
现在的问题就是针对那些面额均小于C的coins该怎么组合？又得回到经典的性价比问题，刚才说了 710 / 6 是最优的，但由于面额的性质可能导致 100 / 10，而非100 / 6，所以我们的策略一定要尽量避免10的大量出现。
这里，我们直接给出第二阶段的贪心策略，但我并不知道为何能够得到最优解，只能证明它的充分性，必要性实在不知道从何下手。
第二阶段策略：
- 对硬币面额从大到小尽量凑得接近C，允许等于或不足C，但是不能超出C。
- 接着按硬币面额从小到大凑满C（凑满的意思是允许超出一个最小面值，ps此处的最小面值指的是硬币剩余量不为0的那些硬币中的最小面值），凑满之后得出了最优解，发掉，继续进入上一步骤循环。
简单证明下：
假设我们从小到大凑足C，那么必然面额小的被用掉，这就导致面额大的在填补C时，有大量的空间无法被小额填满，为了让它超过C，只能用较大额的填，而这就进一步导致面额超过C的部分大大增加，如原本(5+1)元，凑足C=6的情况，损失0，而当1元先被用尽，则导致凑成(5+5)来分发，这就浪费了原先的剩余空间1，而损失了4，显然不划算。
这个问题，也可以类比上一道题，打包问题，我们尽可能的使用少的包裹，就让尽可能多的剩余空间被填补即可，而这策略就是从大到小慢慢塞满即可，此处只是多了一个超出部分，为了让超出部分最小，那一定是从小到大反过来选。
代码如下：
public class SolutionDay24_P3040 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int C = in.nextInt();
int[] V = new int[N];
int[] B = new int[N];
for (int i = 0; i < N; i++){
V[i] = in.nextInt();
B[i] = in.nextInt();
}
System.out.println(solve(V, B, C));
in.close();
}
private static class Coin{
int v;
int b;
Coin(int v, int b){
this.v = v;
this.b = b;
}
@Override
public String toString() {
return "[" + v + "," + b + "]";
}
}
//优先处理面值大的元素
private static int solve(int[] V, int[] B, int C){
int total = 0;
Coin[] coins = new Coin[V.length];
for (int i = 0; i < V.length; i++){
coins[i] = new Coin(V[i],B[i]);
}
Arrays.sort(coins, new Comparator<Coin>() {
@Override
public int compare(Coin o1, Coin o2) {
return o2.v - o1.v;
}
});
for (int i = 0; i < V.length; i++){
if (coins[i].v >= C) {
total += coins[i].b;
coins[i].b = 0;
}
}
int[] need = new int[V.length];
while (true){
int sum = C;
need = new int[V.length];
//从大到小凑
for (int i = 0; i < V.length; i++){
if (coins[i].b > 0 && sum > 0){
int can_use = Math.min(coins[i].b, sum / coins[i].v);
if (can_use > 0){
sum -= can_use * coins[i].v;
need[i] = can_use;
}
}
}
//从小到大凑
for (int i = V.length - 1; i >= 0; --i){
if (coins[i].b > 0 && sum > 0){
int can_use = Math.min(coins[i].b - need[i], sum / coins[i].v + 1);
if (can_use > 0){
sum -= can_use * coins[i].v;
need[i] += can_use;
}
}
}
if (sum > 0){
//剩余硬币凑不满
break;
}
int min_week = 1 << 30;
for (int i = 0; i < V.length; i++){
if (need[i] == 0) continue;
min_week = Math.min(min_week, coins[i].b / need[i]);
}
total += min_week;
for (int i = 0; i < V.length; i++){
if (need[i] == 0) continue;
coins[i].b -= min_week * need[i];
}
}
return total;
}
}POJ 1862: Stripies
这道题就很简单了，简单写下公式你就能明白，当存在三个数时，我们有：
m1+m2+m3≥22m1m2m234−−−−−−−−√−−−−−−−−−−−⎷
m_1 + m_2 + m_3 \ge 2\sqrt{2\sqrt{m_1m_2\frac{m_3^{2}}{4}}}
所以说，为了让根号的值最小，m1m_1和m2m_2应该为最大和次大，而m3m_3应该是最小的，谁叫人家是平方呢？
所以用一个优先队列维持一个最大堆，poll最大和次大，计算一次，把新的值再offer进去，直到最后只剩下一个元素，比较简单。代码如下：
public class SolutionDay24_P1862 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int[] stripe = new int[N];
for (int i = 0; i < N; i++){
stripe[i] = in.nextInt();
}
System.out.println(solve(stripe));
in.close();
}
private static double solve(int[] stripe){
PriorityQueue<Double> queue = new PriorityQueue<>(new Comparator<Double>() {
@Override
public int compare(Double o1, Double o2) {
return (o2-o1) > 0 ? 1 : -1;
}
});
for (int i = 0; i < stripe.length; i++){
queue.offer((double)stripe[i]);
}
while (queue.size() != 1){
double m1 = queue.poll();
double m2 = queue.poll();
queue.offer(collide(m1, m2));
}
return queue.peek();
}
private static double collide(double m1, double m2){
return 2 * Math.sqrt(m1 * m2);
}
}POJ 3262: Protecting the Flowers
一道陷阱题，起初的选牛策略是尽可能的选择d大的，当d相同，选择t长的，对于POJ的测试用例来看无比正确，但其实充满了陷阱。一个简单的选择比较损失如下：
100 9
1 5
乍一看应该先赶9，其实不然，此处应该先赶时间较短的，但不管如何，我们可以在两头牛之间计算损失，怎么算？
就是按照它的法则来：
赶走第一头损失：2*100*5
赶走第二头损失：2*1*9
显然应该赶走第二头，所以两头牛的选择如下,有牛 c1和c2
compare c1.T * c2.D > c1.D * c2.T
到这我就好奇了，为什么针对三头以上，这种选择策略也是正确的呢？假设我们现在有m头牛，如下o1,o2,...,omo_1,o_2,...,o_m，并且已知了第m头牛，和其他m-1头两两比较后，有om.T∗oi.D>oi.T∗om.Do_m.T * o_i.D \gt o_i.T * o_m.D，根据上述公式，说明了在m头牛中，第m头牛是最应该被选的，现在我们假设恰巧第一次移除这第m头牛，所以有：
损失1：2∗om.T(o1.D+o2.D+...+om−1.D)
损失1：2 * o_m.T (o_1.D + o_2.D + ... + o_{m-1}.D)
此时，我们再假设如果不移第m头牛，且把它保留到最后，所以有：
损失2：2∗om.D(o1.T+o2.T+...+om−1.T)
损失2：2 * o_m.D (o_1.T + o_2.T + ... + o_{m-1}.T)
因为我们知道，对于任何i，有om.T∗oi.D>oi.T∗om.Do_m.T * o_i.D \gt o_i.T * o_m.D，所以损失1大于损失2，嘿，把第m头牛保留到最后，损失2都比损失1小，那在某个中间时刻移除第m头牛，损失2将变得更小。所以，不管如何，都应该先移除第m头牛（损失1最大），得证。
所以代码如下：
public class SolutionDay24_P3262 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int[] T = new int[N];
int[] D = new int[N];
for (int i = 0; i < N; i++){
T[i] = in.nextInt();
D[i] = in.nextInt();
}
System.out.println(solve(T, D));
in.close();
}
private static class Pair{
int t;
int d;
Pair(int t, int d){
this.t = t;
this.d = d;
}
}
private static long solve(int[] T, int[] D){
Pair[] p = new Pair[T.length];
int damage = 0;
for (int i = 0; i < T.length; i++){
damage += D[i];
p[i] = new Pair(T[i],D[i]);
}
Arrays.sort(p, new Comparator<Pair>() {
@Override
public int compare(Pair o1, Pair o2) {
return o2.d * o1.t - o1.d * o2.t;
}
});
long total = 0;
for (int i = 0; i < T.length; i++){
damage -= p[i].d;
total += damage * 2 * p[i].t;
}
return total;
}
}