题面
小 Z 是个特别堕落的小朋友，上数学课的时候经常有奇奇怪怪的想法。小 Z 的的包里有块 n*m 的长方形木板，小 Z 想把木板全部切成 1*1 的小正方形（用来玩拼图）。但木板本身并不均匀，因此从不同的线切割下去要花不同的代价。而且对于一块木板，切割一次以后就被分割成两块，而且由于不能把这两块木板拼在一起然后一刀切成四块（动静太大），所以只能两块分别再进行一次切割。现在小 Z 并不想花太多的力气，所以他来找你帮他求一求最小的代价。小 Z 是个特别堕落的小朋友，上数学课的时候经常有奇奇怪怪的想法。小 Z 的的包里有块 n*m 的长方形木板，小 Z 想把木板全部切成 1*1 的小正方形（用来玩拼图）。但木板本身并不均匀，因此从不同的线切割下去要花不同的代价。而且对于一块木板，切割一次以后就被分割成两块，而且由于不能把这两块木板拼在一起然后一刀切成四块（动静太大），所以只能两块分别再进行一次切割。现在小 Z 并不想花太多的力气，所以他来找你帮他求一求最小的代价。
分析
由排序不等式
顺序和>乱序和>逆序和
我们可知，一定要把花费较大的切法放在前面切，因为切的次数是不下降的，而花费较大的放在前面切和不下降的刀数的乘积之和就是逆序和，是最优的。
代码
#include<bits/stdc++.h> using namespace std; #define N 100100 #define ll long long ll n,m,cx=1,cy=1,cnt,ans; struct email { ll w,id; }a[N*4]; template<class T> inline void read(T &x) { x=0;ll f=1;static char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} x*=f; } bool cmp(email a,email b){return a.w>b.w;} int main() { read(n);read(m); for(ll i=1;i<n;i++)read(a[++cnt].w),a[cnt].id=0; for(ll i=1;i<m;i++)read(a[++cnt].w),a[cnt].id=1; sort(a+1,a+1+cnt,cmp); for(ll i=1;i<=cnt;i++) { if(a[i].id==0) ans+=a[i].w*cy,cx++; else ans+=a[i].w*cx,cy++;; } printf("%lld ",ans); return 0; }