题目传送门(BZOJ)

题解 :

切某个方向会使得另一个方向的剩下的刀都多切一次, 故贪心的让代价大的切的次数尽可能少一定最优,
我们把所有的刀都放一起排个序, 模拟一下整个过程统计答案即可

代码 :

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define ll long longusing namespace std;struct CUT { int val, flg; inline int operator < (const CUT &A) const {return val > A.val;}}a[200200];int cnt[2];int main() { ll ans = 0; int n, m; scanf("%d%d", &n, &m); n --, m --; for(int i = 1; i <= n; i ++ ) scanf("%d", &a[i].val); for(int i = 1; i <= m; i ++ ) scanf("%d", &a[i+n].val), a[i+n].flg = 1; sort(a+1, a+n+m+1); for(int i = 1; i <= n+m; i ++ ) ans += (ll)a[i].val * (cnt[a[i].flg^1]+1), cnt[a[i].flg] ++ ; printf("%lld\n", ans);}

本文为Yirannn原创, 转载必须以链接形式注明>原文链接<