Description
有两个表， A 表有m个分区，第 i 个分区有ai行， B 表有n个分区，第 i 个分区有bi行，每次操作可以任一个表的任一分区的一行复制到任意另一个分区里，最后需要满足，对于任意 A 表的一行和任意B表的一行，都存在一个分区包含这两行，问最少进行多少次操作
Input
第一行两个整数 n 和m分别表示两个表的分区数，之后输入 n 个整数ai表示 A 表第i个分区的行数，之后输入 m 个整数bi表示 B 表第i个分区的行数 (1≤n,m≤105,1≤ai,bi≤109)
Output
输出满足条件所需的最少操作数
Sample Input
2 2 2 6 3 100
Sample Output
11
Solution
最优方案对于一个分区里的行的处理是一样的，所以我们只需要考虑对任意 1≤1≤n,1≤j≤m ，存在一个分区有 A 表第i个分区的 ai 行和 B 表第j个分区的 bj 行即可，固定 i ，有两种比较优的策略，要么把B表复制到 A 表第i个分区，要么把 A 表第i个分区复制到最大分区然后把 B 表复制到A表最大分区，对于 A 表的最大分区这两种方案的代价是一样的，对于A表的其他分区，假设是第 i 个分区，那么最小代价是min{∑j=1nbj,ai}，这是把 B 表往A表复制的最优解，把 A 表往B表复制的最优解同理，显然不可能两边来回复制，所以最后从两种策略中选较优的即可
Code
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #include<queue> #include<map> #include<set> #include<ctime> using namespace std; typedef long long ll; #define INF 0x3f3f3f3f #define maxn 111111 int m,n,a[maxn],b[maxn]; int main() { while(~scanf("%d%d",&m,&n)) { ll sum1=0,sum2=0; for(int i=0;i<m;i++)scanf("%d",&a[i]),sum1+=a[i]; for(int i=0;i<n;i++)scanf("%d",&b[i]),sum2+=b[i]; sort(a,a+m),sort(b,b+n); ll ans1=sum2,ans2=sum1; for(int i=0;i<m-1;i++)ans1+=min(sum2,1ll*a[i]); for(int i=0;i<n-1;i++)ans2+=min(sum1,1ll*b[i]); printf("%I64d\n",min(ans1,ans2)); } return 0; }