921519_10125.c

ACM 第10125 題 Sumsets

#include<stdio.h>
#include<stdlib.h>
/*#include<conio.h>*/
int itemp1[1000005];
int iSub[1000005][3];
/*Sumsets  */
struct a_b{
    int a;
    int b;
    int X;
}iAdd[1000005];
int comp(const void *obj1,const void *obj2)
{
    int *p_obj1=(int*)obj1,
        *p_obj2=(int*)obj2;
    if((*p_obj1)>(*p_obj2))  
        return 1;
    else if((*p_obj1)<(*p_obj2)) 
        return -1;
    else
        return 0;     
}
void Sort2(struct a_b iAdd[],int left,int right)
{
    int pivot,temp1;
    if(left<right)
    {
        int i=left;
        int j=right+1;
        pivot=iAdd[left].X;
        do{
			do i++;while(iAdd[i].X<pivot);
			do j--;while(iAdd[j].X>pivot);
			if(i<j)
            {
				temp1=iAdd[i].X;
				iAdd[i].X=iAdd[j].X;
				iAdd[j].X=temp1;
				
				temp1=iAdd[i].a;
				iAdd[i].a=iAdd[j].a;
				iAdd[j].a=temp1;
				
				temp1=iAdd[i].b;
				iAdd[i].b=iAdd[j].b;
				iAdd[j].b=temp1;
            }
         }while(i<j);
         temp1=iAdd[left].X;
         iAdd[left].X=iAdd[j].X;
         iAdd[j].X=temp1;
         
         temp1=iAdd[left].a;
		 iAdd[left].a=iAdd[j].a;
	     iAdd[j].a=temp1;
	     
		 temp1=iAdd[left].b;
		 iAdd[left].b=iAdd[j].b;
		 iAdd[j].b=temp1;
         
         Sort2(iAdd,left,j-1);
         Sort2(iAdd,j+1,right);
    }
}
int bin_search(int ss,int j,int mx)
{
    int upper,lower,mid;
    upper = mx;
    lower = 0;
    while(lower!=upper){
        mid=(upper +lower)/2;
        if(iAdd[mid].X>=ss)
            upper = mid;
        else
            lower = mid+1;
    }
    if(iAdd[lower].X==ss){
        if(iAdd[lower].a!=iAdd[lower].b&&
           iAdd[lower].a!=iSub[j][0]&&
           iAdd[lower].a!=iSub[j][1]&&
           iAdd[lower].b!=iSub[j][0]&&
           iAdd[lower].b!=iSub[j][1]&&
           iSub[j][0]!=iSub[j][1]
           ){
            return 1;
        }
        else
            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);     
        if(iline==0)
            break;
        else{
            for(i=0;i<iline;i++){
                scanf("%d",&itemp1[i]);
            }
        }
        qsort(itemp1,iline,sizeof(int),comp);
        
        iFlag = 0;
        for(i=0;i<iline;i++){
            for(j=i+1;j<iline;j++){
                iAdd[itemp3].a=itemp1[i];
                iAdd[itemp3].b=itemp1[j];
                iAdd[itemp3].X=itemp1[i]+itemp1[j];
                itemp3++;
            }
        }  
        Sort2(iAdd,0,itemp3-1);
        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(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;
}