hdu6168 Numbers 2017多校1008 map

http://acm.split.hdu.edu.cn/showproblem.php?pid=6168

題意：由一個a數組，通過ai+aj(1<=i<j<=n)構成b數組。現在給你a和b數組的混合，求a數組。

題解：每次存入時，用map标記每個數字的出現次數(資料是從小到大給的，是以可以不用排序)。然後前兩個數開始相加，然後更新map(感覺有點篩法的意思)。更新之後，如果map中這個數還出現，就記入答案并更新map。

代碼：

#include<bits/stdc++.h>
#define debug cout<<"aaa"<<endl
#define d(a) cout<<a<<endl
#define mem(a,b) memset(a,b,sizeof(a))
#define LL long long
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define MIN_INT (-2147483647-1)
#define MAX_INT 2147483647
#define MAX_LL 9223372036854775807i64
#define MIN_LL (-9223372036854775807i64-1)
using namespace std;

const int N = 500 + 5;
const int mod = 1000000000 + 7;
const double eps = 1e-8;
int a[130000];
map<int,int> m;

int main(){
	int n,ans[N],cnt;
	while(~scanf("%d",&n)){
		m.clear(),mem(ans,0),cnt=3;
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			m[a[i]]++;
		}
		ans[1]=a[1],ans[2]=a[2];
		m[a[1]]--,m[a[2]]--,m[a[1]+a[2]]--;
		for(int i=3;i<=n;i++){
			if(m[a[i]]!=0){//計入答案，并更新map
				ans[cnt]=a[i];
				m[a[i]]--;
				for(int j=1;j<cnt;j++){
					m[ans[cnt]+ans[j]]--;
				}
				cnt++;
			}
		}
		printf("%d\n",cnt-1);
		for(int i=1;i<cnt-1;i++){
			printf("%d ",ans[i]);
		}
		printf("%d\n",ans[cnt-1]);
	}
	return 0;
}