摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

作法 :

C的MAP有點麻煩

所以就用快速排序+二分搜尋囉

/********************************************************/

#include<stdio.h>
#include<stdlib.h>
int partition(int[], int, int);   
void quicksort(int[], int, int);
int num[10001]={0};
int index1(int n,int L,int L2)  
{  
 int lower=L2, mid, high=L-1;  
 int index=-1;  
    do   /*二分搜尋*/ 
    {  
      mid=(lower+high)/2;  
      if(num[mid]<n)     lower=mid+1;  
      else if(num[mid]>n)  high=mid-1;  
      else  index=mid;  
    }  
    while(index==-1&&lower<=high);  
  return index;  
} 
int input()  
{  
  char cha;  
  int x=0;  
  while(cha=getchar())  
     if(cha!=' '&&cha!='\n') break;  
  x=cha-48;  
  while(cha=getchar())   
    {  
     if(cha==' '||cha=='\n') break;  
      x=x*10+cha-48;  
    }  
    return x;  
}
main()
{
 int n,m,k,a,b;
 while(scanf("%d",&n)==1)
    {
       for(a=0;a<n;a++)
         num[a]=input();
       quicksort(num,0,n-1);
       scanf("%d",&m);
       for(a=n;a>=0;a--)
         {
           int index=index1(m-num[a],n,a+1);
           if(index!=-1)
              {
                 printf("Peter should buy books whose prices are %d and %d.\n\n",num[a],m-num[a]);
                 break;
              }
         } 
    }
 return 0;
}
int partition(int num[],int left,int right)   
{  
  int a=left-1,b,s=num[right];  
  for(b=left;b<right;b++)  
   {  
     if(num[b]<s)  
       {  
         a++;  
         int temp;  
         temp=num[a];  
         num[a]=num[b];
         num[b]=temp;   
       }   
   }   
         int temp;  
         temp=num[a+1];
         num[a+1]=num[right];  
         num[right]=temp;
   return a+1;   
}   
void quicksort(int num[],int left,int right)  
{  
 int q;  
 if(left<right)   
   {  
     q=partition(num,left,right);  
     quicksort(num,left,q-1);  
     quicksort(num,q+1,right);   
   }   
}