一个集合中需要找到 a,b,c,d ,使得 a+b+c=d
枚举a,b ,计算a+b,存在map里
再枚举d,c ,计算d-c 是否 存在 d-c==a+b
#include <iostream> #include <map> #include <algorithm> #include <vector> using namespace std; const int N=1e3+2; //a+b==d-c #define pii pair<int,int> #define mk(x,y) make_pair(x,y) int n; map<int,vector<pii> > mp; int a[N]; int H(){ int i,j; for(j=n;j>0;j--) for(i=j-1;i>0;i--){ int t=a[j]-a[i]; for(int k=0;k<mp[t].size();k++){ int xx=mp[t][k].first,yy=mp[t][k].second; if(xx!=a[i]&&yy!=a[j]&&xx!=a[j]&&yy!=a[i]) return j; } } return -1; } void sov(){ int i,j; for(i=1;i<=n;++i) cin>>a[i];sort(a+1,a+1+n); for(i=1;i<=n;i++) for(j=i+1;j<=n;j++) mp[a[i]+a[j]].push_back(mk(a[i],a[j])); int t=H(); if(t==-1) cout<<"no solution"<<endl; else cout<<a[t]<<endl; } signed main(){ while(cin>>n,n){ mp.clear() ; sov(); } }
标签:int,pair,UVA,include,Sumsets,10125 From: https://www.cnblogs.com/towboa/p/17323406.html