题解/算法 {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;
}
你可能有疑问,你的排序规则 只是针对于 任意相邻的元素, 而我们知道一个序列要排序 他的所有元素需要是全序的 而你这里 你不符合传递性 (注意他不是偏序 偏序是符合传递性的),即你得到了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;
}
这是错误的, 比如[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]
);