CF memsql Start[c]UP 2.0 B
B. Distributed Join
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Piegirl was asked to implement two table join operation for distributed database system, minimizing the network traffic.
Suppose she wants to join two tables, A and B. Each of them has certain number of rows which are distributed on different number of partitions. Table A is distributed on the first cluster consisting of m partitions. Partition with index i has ai rows from A. Similarly, second cluster containing table B has n partitions, i-th one having bi rows from B.
In one network operation she can copy one row from any partition to any other partition. At the end, for each row from A and each row from B there should be a partition that has both rows. Determine the minimal number of network operations to achieve this.
Input
First line contains two integer numbers, m and n (1 ≤ m, n ≤ 105). Second line contains description of the first cluster with m space separated integers, ai (1 ≤ ai ≤ 109). Similarly, third line describes second cluster with n space separated integers, bi (1 ≤ bi ≤ 109).
Output
Print one integer — minimal number of copy operations.
Sample test(s)
input
2 2
2 6
3 100
output
11
input
2 3
10 10
1 1 1
output
6
Note
In the first example it makes sense to move all the rows to the second partition of the second cluster which is achieved in 2 + 6 + 3 = 11operations
In the second example Piegirl can copy each row from B to the both partitions of the first cluster which needs 2·3 = 6 copy operations.
简单贪心，题意不是很好理解。。
大致题意：
A有m个分支，每个分支有ai组，B有n个分支，每个分支有bi组，要将A与B合并（A的每个分支都包含B的全部，或B的每个分支都包含A的全部），使得总花费最小。
贪心策略：将a数组升序排列，b数组升序排列，求出a的和ma，b的和mb。一共就两种情况，要么将A合并到B，要要么将B合并到A，取两者的小值即可。如果是将B合并到A中，我们就将a数组遍历一下，a[i]>=mb就保留a[i],将mb合并到a[i]中，花费为mb，否则，将a[i]合并到A的其他组中，花费为a[i]，注意一点如果是a的最后一项必须保留，哪怕是比mb小，也要保留下来，将mb合并进来，因为是将B合并到A，A中应该至少保留一项。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<stdlib.h>
#include<vector>
#include<cstring>
#include<map>
#include<algorithm>
#include<string.h>
#define M(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
using namespace std;
int n,m;
int a[],b[];
int main()
{
while(scanf("%d%d",&n,&m)==)
{
for(int i = ;i<n;i++)
scanf("%d",&a[i]);
for(int i = ;i<m;i++)
scanf("%d",&b[i]);
sort(a,a+n);
sort(b,b+m);
long long sum = ;
long long ans = ;
if(a[n-]<b[m-])
{
for(int i = ;i<n;i++)
sum+=a[i];
for(int i = ;i<m-;i++)
{
if(sum>b[i])
ans+=b[i];
else
ans+=sum;
}
ans+=sum;
}
else
{
for(int i = ;i<m;i++)
sum+=b[i];
for(int i = ;i<n-;i++)
{
if(sum>a[i])
ans+=a[i];
else
ans+=sum;
}
ans+=sum;
}
printf("%I64d\n",ans);
}
return ;
}