题解/算法 {3219. 切蛋糕的最小总开销 II}_leetcode 3219

题解/算法 {3219. 切蛋糕的最小总开销 II}

@LINK: https://leetcode.cn/problems/minimum-cost-for-cutting-cake-ii/;

令M为你需要横切的次数 N为竖切的次数, 我们令h表示水平切 v表示竖切, 那么 对于某个水平切hi 令此时已经有了x次竖切 那么此时你要水平切的次数是x+1次 即代价是hi * (x+1);
你一共需要切M+N刀 即一个长度是M+N的序列 由h1,h2,...,hm 和 v1,v2,...,vn组成; 他的代价是: { hi*(该hi前面v的个数+1) }之和 + { vi*(该vi前面h的个数+1) }之和;

就是这么个式子, 我们将h序列 v序列分开讨论 比如对于h序列 从前往后每个元素的代价是h1*c1 + h2*c2 + ... 从上面式子可知 ci是单调递增的 即c1<=c2<=..., 因此 要让代价最小 hi序列一定是单调递减的;

即此时 将hi, vi从大到小排序 那么hi在最终序列中的相对位置就确定了, 然后剩下的唯一问题是 怎么确定hi,vi的次序;

此时用到 涉及序列排序时 一个贪心算法常用的方法 交换两个(相邻的)元素;
比如对于答案序列A, 我们尝试交换两个元素 (当然根据上面分析 肯定是一个hi 一个vi), 并且 他俩在A中是相邻的 (因为如果不是相邻的 我们可以通过若干次 交换相邻元素 从而做到 交换两个不相邻元素);
对于PRE hi vi ... (PRE里由CV个v和CH个h), 我们只计算hi,vi的贡献 (因为交换他俩 不影响其他元素的贡献), 等于 (CV + 1) * hi + (CH + 2) * vi;
而对于PRE vi hi ..., 他俩的贡献是 (CV+2) * hi + (CH+1) * vi;
化简前后两个式子 会得到cmp(前式, 后式) = cmp(vi, hi), 因此 如果hi < vi 此时后式是更小的 即需要交换; (即hi,vi序列是递减的 而对于相邻的hi,vi 他也是递减的, 换句话说 整个答案序列是递减的);

long long minimumCost( int, int, vector<int>& H, vector<int>& V) {
    long long ANS = 0;
    vector< pair<int,bool> > A;  A.reserve( H.size() + V.size());
    for( auto i : H){ A.emplace_back( i, 1);}  for( auto i : V){ A.emplace_back( i, 0);}
    std::sort( A.begin(), A.end(), []( auto const& _a, auto const& _b)->bool{
        return _a.first > _b.first;
    });
    int cont[2] = {0,0};
    for( auto & a : A){
        ANS += (cont[a.second ^ 1] + 1) * a.first;
        cont[ a.second] ++;
    }
    return ANS;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

你可能有疑问，你的排序规则 只是针对于 任意相邻的元素， 而我们知道一个序列要排序 他的所有元素需要是全序的 而你这里 你不符合传递性 （注意他不是偏序 偏序是符合传递性的），即你得到了a<b,b<c 但是你没有得到a<c 因为你没有证明传递性；
证明： 你分析时的那个答案序列 他其实不是特定的，换句话说 你得到a<b,b<c 其实你并不知道a,b,c具体是什么， 即 虽然我们分析的是相邻元素的比较规则 但其实 由于你假设的这个答案序列 是未知的 他具普遍性；
. 比如说[0]<[1], [1]<[2], 然后对于某个序列A: [x1,x2,T] 此时根据比较规则[1]<[2]， 你可以得到新序列A1: [x1,T,x2] 于是再根据比较规则[0]<[1]，又得到新序列A2: [T,x1,x2]， 因此虽然我们不知道[0]<[2] 但其实由于你假设的序列 不是具体唯一的（即我们不是针对A这一个序列 可以发现我们还得到了A1,A2序列 即序列是一直在变化的），当然 本质上说 你得到[0]<[1], [1]<[2] 其实他是具有传递性的；

@DELI;

#看一个错误做法#
对于PRE [?] ... (设PRE里有CV个v和CH个h), 我们研究此时 hi,vi谁放到[?]的位置； 如果hi放在这 (CV+1)*hi是他自身的贡献 然后他还会使得后面的所有vi的代价都增加一个vi，同样如果hi放在这里 分析也一样；
然后我们从[0]开始 用两个指针对vi,hi序列遍历（vi,hi已经是递减的了）通过上面式子 看把哪个元素放到这个位置上， 即以下代码：

long long minimumCost(int M, int N, vector<int>& H, vector<int>& V) {
    --M, --N;
    long long ANS = 0;
    int sumH = std::accumulate( H.begin(), H.end(), 0);
    int sumV = std::accumulate( V.begin(), V.end(), 0);
    std::sort( H.begin(), H.end(), std::greater<>());
    std::sort( V.begin(), V.end(), std::greater<>());
    int m = 0, n = 0;
    for( ; m<M || n<N; ){
        bool useH;
        if( n >= N){ useH = 1;}
        else if( m >= M){ useH = 0;}
        else{
            Int64_ valH = (n+1)*1LL*H[m] + sumV;
            Int64_ valV = (m+1)*1LL*V[n] + sumH;
            useH = (valH < valV);

        }

        if( useH){
            ANS += (n+1) *1LL* H[m];  sumH -= H[m];
            ++ m;
        }
        else{
            ANS += (m+1) *1LL* V[n];  sumV -= V[n];
            ++ n;
        }
    }
    return ANS;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

这是错误的， 比如[3,1]， [5] 你会得到[3,...] （代码是3+5） 而答案是[5,...]（代价是5+4） (更具体的 你得到[3,1,5] 而答案是[5,3,1]）；
为啥呢？ 你无法保证后效性，你在假设[3,...]这种情况时 你计算了+=5 也就是代码中的sumV，但是问题在于 你的前提建立在你认为5已经是在3后面了（当然因为你知道5一定会在3后面 所以这样假设），可是 其实不能只是+= sumV这么简单 你还要知道5的确切位置 即(CH * 1) * 5 你只计算了1*5这项 而实际上 你还要考虑CH*5这项；（当然这是做不到的 因为你根本无法求出CH);
. 举个例子, 为什么会得到[3,1,?] 而不是[3,5,?]呢? 因为你放1 你计算的代价是1 + 5 而放5 代价是2*5 + 1, 为什么会有这个2*5他都这么大了 为什么还轮不到他, 就是因为 你前面放3时 就没考虑5的确切位置 就考虑了一个+=5 导致他一直在后面 轮不到他; (即[10,9,8,7,...] 和 [100] 正确答案是[100, 10,...] 而你的答案是[10,9,8,..., 100]);