1737.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1737 on 2006-07-24 at 17:52:09 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 102400;

int w, h, wn[N], hn[N];

int main()
{
	int i, j;
	
	while(scanf("%d %d", &w, &h) != EOF) {
		for(i = 0; i < w; i++) scanf("%d", &wn[i]);
		for(i = 0; i < h; i++) scanf("%d", &hn[i]);
		sort(wn, wn+w); sort(hn, hn+h);
		if(wn[w-1] != hn[h-1]) { printf("No solution.\n"); continue; }
		int inf = 0, sup = 0, sum[N] = { 0 };
		for(i = 1; i <= h; i++) sum[i] = sum[i-1]+hn[i-1];
		for(i = w, j = h; i != 0 && j != 0; )
			if(wn[i-1] == hn[j-1]) { i--; j--; inf += wn[i]; }
			else if(wn[i-1] > hn[j-1]) inf += wn[--i];
			else inf += hn[--j];
		while(i != 0) inf += wn[--i];
		while(j != 0) inf += hn[--j];
		for(i = 0; i < w; i++) {
			int uo = upper_bound(hn, hn+h, wn[i])-hn;
			sup += sum[uo]+wn[i]*(h-uo);
		}
		printf("%d %d\n", inf, sup);
	}
	
	return 0;
}