题目：HDU-1085

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1085

题目：

Big Event in HDU

  

   2
10 1
20 1
3
10 1 
20 2
30 1
-1
  

  

   20 10
40 40
  

额，这个题我还是用了母函数做的，这个构造的多项式以价值为指数，和其他的一样，只不过在得出结果以后我先筛选出非0的结果，排序以后再一个个比较哪个最接近，数据比较小所以也还好，没超时。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<math.h>
#include<cstdio>
using namespace std;
const int maxn= 250005;
int a[maxn],b[maxn];
int n;
int v,m,t;
int counts;
int maxNum,ans1,ans2;
int main(){
	while(cin>>n){
		if(n<0) break;
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		cin>>v>>m;
		for(int i=0;i<=m;i++)
			a[i*v]=1;
		t=v*m;
		for(int i=1;i<n;i++){
			cin>>v>>m;
			t+=v*m;
			for(int j=0;j<=t;j++)
				for(int k=0;k<=v*m;k+=v)
					b[j+k]+=a[j];
			for(int j=0;j<=t;j++){
				a[j]=b[j];
				b[j]=0;
			}
		} //以上为构建母函数得出结果
		counts=0;
		for(int i=1;i<=t;i++){                        //筛选非0解
			if(a[i]!=0)
				b[counts++]=i;
		}
		sort(b,b+counts);                           //排序，其实不排也没什么
		maxNum=maxn;
		for(int i=0;i<counts;i++){                  //记住保证大的一堆在前面
			if(t-b[i]>=b[i]){
				if(t-b[i]-b[i]<maxNum){
					maxNum=t-b[i]-b[i];
					ans1=t-b[i];
					ans2=b[i];
				}
			}
			else{
				if(2*b[i]-t<maxNum){
					maxNum=2*b[i]-t;
					ans1=b[i];
					ans2=t-b[i];
				}
			}
		}
		cout<<ans1<<" "<<ans2<<endl;
	}
	return 0;
}