贪心：交换论证法

目录

切蛋糕的最小总开销

切蛋糕的最小总开销

交换论证：

设横切的开销为 h，如果先横切，设需要横切 cnt_h 次。

设竖切的开销为 v，如果先竖切，设需要竖切 cnt_v 次。

先横切，再竖切，那么竖切的次数（这一刀经过的蛋糕块数）要多 1，开销为
h⋅cnt_h+v⋅(cnt_v+1)
先竖切，再横切，那么横切的次数（这一刀经过的蛋糕块数）要多 1，开销为
v⋅cnt_v+h⋅(cnt_h+1)
如果先横再竖开销更小，则有

h⋅cnt_h+v⋅(cnt_v+1)<v⋅cnt_v+h⋅(cnt_h+1)
化简得

h>v
这意味着，谁的开销更大，就先切谁。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/*
1. 最小总开销=一堆横切竖切开销的和
2. 非一切到底的开销=一切到底的开销
3. cnt_h表示横切次数，cnt_v表示竖切次数
4. 竖切横切，谁的开销大，就先切谁
*/

class Solution {
public:
    long long minimumCost(int m, int n, vector<int>& horizontalCut, vector<int>& verticalCut) {
        long long res=0;
        sort(horizontalCut.begin(),horizontalCut.end(),greater<>());//开销大的在前
        sort(verticalCut.begin(),verticalCut.end(),greater<>());
        int cnt_h=1;//横切次数
        int cnt_v=1;//竖切次数
        int i=0,j=0;
        while(i<m-1||j<n-1){
            if(j==n-1||i<m-1&&horizontalCut[i]>verticalCut[j]){//竖切全部完成或横切开销大于竖切开销
                res+=horizontalCut[i]*cnt_v;//横切
                cnt_h++;
                i++;
            }
            else{
                res+=verticalCut[j]*cnt_h;
                cnt_v++;
                j++;
            }
        }
        return res;
    }
};