10125.c

ACM 第10125 題 Sumsets

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>

int itemp1[10000000];
int iAdd[10000000][3],iSub[10000000][3];

int bin_search(int ss,int j,int mx)
{
    int upper,lower,mid;
    upper = mx;
    lower = 0;
    /*printf("upper =%d lower =%d\n",upper,lower);*/
    while(lower!=upper){
        /*printf("a");*/
        mid=(upper +lower)/2;
        if(iAdd[mid][2]>=ss)
            upper = mid;
        else
            lower = mid+1;
    }
    
    if(iAdd[lower][2]==ss){
        /*printf("a");*/
        if(iAdd[lower][0]!=iAdd[lower][1]&&
           iAdd[lower][0]!=iSub[j][0]&&
           iAdd[lower][0]!=iSub[j][1]&&
           iAdd[lower][1]!=iSub[j][0]&&
           iAdd[lower][1]!=iSub[j][1]&&
           iSub[j][0]!=iSub[j][1]
           ){
            /*printf("a");*/
            return 1;
        }
    }
    else
        return -1;  
}
int main()
{
    int iline;
    int itemp2,itemp3,itemp4;
    int i,j;
    int iFlag;
    int max;
    freopen("data.txt","r",stdin);
    while(1)
    {
        itemp3 = 0,itemp4 = 0;
        scanf("%d",&iline);
        /*printf("iline\%d\n",iline);*/
        if(iline==0)
            break;
        else{
            for(i=0;i<iline;i++){
                scanf("%d",&itemp1[i]);
            }
        }
        /*for(i=0;i<iline;i++){
            for(j=0;j<iline-i-1;j++){
                    if(itemp1[j]>itemp1[j+1]){
                        itemp2=itemp1[j];
                        itemp1[j]=itemp1[j+1];
                        itemp1[j+1]=itemp2;
                    }
            }
        }*/
        iFlag = 0;
        for(i=0;i<iline;i++){
            for(j=i+1;j<iline;j++){
                iAdd[itemp3][0]=itemp1[i];
                iAdd[itemp3][1]=itemp1[j];
                iAdd[itemp3][2]=itemp1[i]+itemp1[j];
                itemp3++;
            }
        }
        for(i=0;i<itemp3;i++){
            for(j=0;j<itemp3-i-1;j++){
                    if(iAdd[j][2]>iAdd[j+1][2]){
                        itemp2=iAdd[j][2];
                        iAdd[j][2]=iAdd[j+1][2];
                        iAdd[j+1][2]=itemp2;
                        itemp2=iAdd[j][1];
                        iAdd[j][1]=iAdd[j+1][1];
                        iAdd[j+1][1]=itemp2;
                        itemp2=iAdd[j][0];
                        iAdd[j][0]=iAdd[j+1][0];
                        iAdd[j+1][0]=itemp2;
                    }
            }
        }
       /*for(i=0;i<itemp3;i++)
            printf("%d\n",iAdd[i][2]);*/
        for(i=0;i<iline;i++){
            for(j=i+1;j<iline;j++){
                iSub[itemp4][0]=itemp1[i];/*c*/
                iSub[itemp4][1]=itemp1[j];/*d*/
                iSub[itemp4][2]=itemp1[j]-itemp1[i];
                itemp4++;
            }
        }
        /*for(i=0;i<itemp3;i++)
            printf("iSub=%d\n",iSub[i][2]);*/
        for(j=0;j<itemp4;j++){
            if(bin_search(iSub[j][2],j,itemp4)==1){
                if(iFlag==0){
                    max=iSub[j][1];
                    iFlag=1;
                }
                else{
                    if(iSub[j][1]>max){
                        max=iSub[j][1];
                    }
                }
            }
        }
        if(iFlag == 0){
            printf("no solution\n");
        }
        else{
            printf("%d\n",max);
        }
    }
    getch();
    return 0;
}