448      iPhone_iPad_Mac_apple

uva 10125 - Sumsets

    本來這幾天不打算寫題了，但是發現太無聊。

    這題一開始直接dfs，果斷超時，加個搜到就跳出，直接WA了，因為例如1 4 5 6 7這樣數列，7 6 1<4 5 6所以直接dfs循環是不行的 

    然後就a+b=d-c n^2的複雜度，不想用hash，於是就二分，結果忘記排序，WA了好多次……

/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <map>
#include <queue>
#define INF 100000000000ll
using namespace std;
long long org[1005];
long long add[1000010];
int ke[1000010][2];
bool bsearch(int i,int j,int l,int r)
{
    int mid;
    long long aim=org[i]-org[j];
    while(l<r)
    {
        mid=(l+r)>>1;
        if(add[mid]<aim)l=mid+1;
        else if(add[mid]==aim)
        {
            while(add[mid]==aim&&mid>=0)mid--;//找到最左邊的相等下標
            mid++;
            while(add[mid]==aim&&(ke[mid][0]==i||ke[mid][0]==j||ke[mid][1]==i||ke[mid][1]==j)) mid++;
            if(add[mid]==aim) return 1;
            else return 0;
        }
        else r=mid;
    }
    return 0;
}
int main()
{
    int n,i,j,now;
    while(~scanf("%d",&n)&&n)
    {
        for(i=0;i<n;i++)
         scanf("%lld",&org[i]);
        now=0;
        sort(org,org+n);
        for(i=0;i<n;++i)
          for(j=i+1;j<n;++j)
          {
              if(org[i]==org[j])continue;
              ke[now][0]=i;ke[now][1]=j;
              add[now++]=org[i]+org[j];
          }
        sort(add,add+now);
        bool flag=1;
        for(i=n-1;i>=0&&flag;i--)
         for(j=0;j<n&&flag;j++)
         {
            if(org[i]==org[j])continue;
            if(bsearch(i,j,0,now))flag=0;
         }
        if(flag)printf("no solution\n");
        else printf("%lld\n",org[i+1]);
    }
}

最後更新：2017-04-04 02:25:10

  上一篇： IBM：這 20 大夢幻般技術 5 年內有望實現

  下一篇： java中使用switch case報錯case expressions must be constant expressions