[UVA] 10125 - Sumsets

題目連結

題意:

給你一堆數字，
問能不能找到 a + b + c =  d，
如果可以，求出 最大的 d。
--------------------------------------------------

我的作法:

把柿子變成 a + b = d - c，
然後窮舉 a b 算出 A= a+b 再 窮舉 d c 算出 B= d-c，
如果有A等於B再去判斷 a b 是否有任一個數是c d，
例如:
1 , 5 , 11 , 13
可以找到
A = 1 + 5 = 6，
B = 11 - 5 = 6 ，
雖然A=B，
但其實 5 是同一個，所以是找不到 a + b + c = d 的可能!
--------------------------------------------------
/* 20151010
 * hanting
 * UVa 10125 - Sumsets
 * C++
 */
#include <iostream>
#include <vector>
#include <map>
#include <algorithm> //find
using namespace std;
int main()
{
    int N;
    while(cin>>N and N)
    {
        int num[N];
        for(int i=0;i<N;i++)
        {
            cin>>num[i];
        }
        bool No=true;
        int maxi=-0x7fffffff;
        /*a+b*/
        map<int,vector<pair<int,int> > > ADD;
        for(int i=0;i<N;i++)
        {
            for(int j=i+1;j<N;j++)
            {
                int add=num[i]+num[j];
                ADD[add].push_back(pair<int,int>(i,j));
            }
        }
        /*d-c*/
        for(int i=0;i<N;i++)
        {
            for(int j=0;j<N;j++)
            {
                if(i!=j)
                {
                    int sub=num[i]-num[j];
                    for(int k=0;k<ADD[sub].size();k++)
                    {
                        int tmpi=ADD[sub][k].first , tmpj=ADD[sub][k].second;
                        if(i!=tmpi and i!=tmpj and j!=tmpi and j!=tmpj)
                        {
                            No=false;
                            maxi=max(maxi,num[i]);
                            break;
                        }
                    }
                }
            }
        }
        if(No)
            cout<<"no solution"<<endl;
        else
            cout<<maxi<<endl;
    }
    return 0;
}