View Code of Problem 133

//普通暴力解法时间复杂度为O(n^2),所以使用快速排序优化 
#include<stdio.h>
void quicksort(int R[],int low,int high){    //快速排序 
	int temp;
	int i=low,j=high;
	if(low<high){
		temp=R[low];
		while(i<j){
			while(j>i&&R[j]>=temp)
			j--;
			if(i<j){
				R[i]=R[j];
				i++;
			}
			while(i<j&&R[i]<temp)
			i++;
			if(i<j){
				R[j]=R[i];
				j--;
			}
		}
	    R[i]=temp; 
	    quicksort(R,low,i-1);
	    quicksort(R,i+1,high);
	}
} 
int main(){
     int T;
     int n,X; 
     int a[100000];
	 scanf("%d",&T);
	 while(T--){
	 	  scanf("%d %d",&n,&X); 
	 	  for(int i=0;i<n;i++)
	         scanf("%d",&a[i]);
	         
	      quicksort(a,0,n-1);           //先把数组排序一下
		  
		  int  index1=0,index2=n-1;
		  while(index1<index2){
		  	if(a[index1]+a[index2]==X&&index1<index2){    
			  	printf("YES\n");
				break; 
			  }
			else if(a[index1]+a[index2]<X&&index1<index2)   
			    index1++;
			else 
			    index2--; 
		  }
		  if(index1==index2)
		  	printf("NO\n");
		  }
	}