pku2928.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <algorithm>
using namespace std;

const int maxn = 100010;
int n[maxn], m[maxn], sumn[maxn];
int N, M;
int c, C;

void init()
{
	int i;
	for (i = 0; i < M; i++)
		scanf("%d", &m[i]);
	for (i = 0; i < N; i++)
		scanf("%d", &n[i]);
	sumn[0] = 0;
	sort(m, m + M);
	sort(n, n + N);
	for (i = 0; i < N; i++)
		sumn[i+1] = sumn[i]+n[i];
}

void solve()
{
	int min, max;
	int i, j;
	if (n[N-1] != m[M-1])
	{
		printf("Impossible\n");
		return;
	}
	if (N < M)
	{
		min = 0;
		for (i = 0, j = 0; i < M; i++)
		{
			min += m[i];
			while (j < N && n[j] < m[i])
				min += n[j++];
			while (j < N && n[j] == m[i])
				j++;
		}
		printf("Minimum: %d, ", min * c);
	}
	else
	{
		min = 0;
		for (i = 0, j = 0; i < N; i++)
		{
			min += n[i];
			while (j < M && m[j] < n[i])
				min += m[j++];
			while (j < M && m[j] == n[i])
				j++;
		}
	}
	i = M - 1;
	j = N - 1;
	max = 0;
	while (i >= 0)
	{
		while (j >= 0 && m[i] < n[j])
			j--;
		max += sumn[j + 1] + (N-j-1) * m[i];
		i--;
	}
	printf("Minimum: %d, maximum: %d\n", min * c, max * C);
}

int main()
{
	while (4 == scanf("%d %d %d %d", &M, &N, &c, &C))
	{
		init();
		solve();
	}
	return 0;
}