Problem C - Sumsets

Problem C - Sumsets

时间： 1ms        内存：128M

描述：

Problem C - Sumsets

Given S, a set of integers, find the largest d such that a + b + c = d where a, b, c, and d are distinct elements of S.

输入：

Several S, each consisting of a line containing an integer 1 <= n <= 1000 indicating the number of elements in S, followed by the elements of S, one per line. Each element of S is a distinct integer between -536870912 and +536870911 inclusive. The last line of input contains 0.

输出：

For each S, a single line containing d, or a single line containing "no solution".

示例输入：

5
2 
3 
5 
7 
12
5
2 
16 
64 
256 
1024
0

示例输出：

12
no solution

提示：

参考答案（内存最优[1728]）：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

int c,i,j,k,n,wn;

char w[10001][100], buf[1000];

int main(){
   
   while (1 == scanf("%d",&n)) {
      if (c++) printf("\n");
      wn = 0;
      for (;;) {
         if (1 != scanf("%[^a-zA-Z]",buf)) break;
         if (1 != scanf("%[a-zA-Z]",buf)) break;
         if (!strcmp(buf,"EndOfText")) break;
         for (i=0;buf[i];i++) buf[i] = tolower(buf[i]);
         strcpy(w[wn++],buf);
      }
      qsort(w,wn,100,strcmp);
      strcpy(w[wn++],"***");
      strcpy(buf,"$$$");
      for (i=j=0;i<wn;i++) {
         if (strcmp(buf,w[i])) {
            if (strcmp(buf,"$$$") && k == n) printf("%s\n",buf),j=1;
            strcpy(buf,w[i]);
            k = 0;
         }
         k++;
      }
      if (!j) printf("There is no such word.\n");
   }
}

参考答案（时间最优[11]）：

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
int n,num[1005];

void solve()
{
    for(int d=n-1;d>=0;d--)
    {
        for(int c=n-1;c>=0;c--)
    {
        if(c==d)
        {
            continue;
        }
        int t=num[d]-num[c];
        int a=0,b=c-1;
        while(a<b)
        {
            if(num[a]+num[b]==t)
            {
                cout<<num[d]<<endl;
                return ;
            }
            else
                if(num[a]+num[b]<t)
            {
                a++;
            }
            else
            {
                b--;
            }
        }
    }
    }

    cout<<"no solution"<<endl;
}
int main()
{

    while((cin>>n),n)
    {
          for(int i=0;i<n;i++)
        cin>>num[i];
    sort(num,num+n);
    solve();
    }

    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。