Description

給出一個(gè)整數(shù)S,另外給出n個(gè)數(shù),判斷是否可以從中取出2個(gè)數(shù),使得這兩個(gè)數(shù)的和是S。

Input

第一行有個(gè)整數(shù)T(1 <= T <= 30),代表數(shù)據(jù)組數(shù)。

對(duì)于每組數(shù)據(jù),第一行包含兩個(gè)整數(shù)S(1 <= S <= 1000000)，n(1 <= n <= 100000)。第二行包含n個(gè)整數(shù)，整數(shù)的范圍為[1,1000000]。

#include "stdio.h"#include "stdlib.h"#include "math.h"/*  思路：本題其實(shí)就是使用暴力破解的方式，但是我們會(huì)發(fā)現(xiàn)超時(shí) 因此要進(jìn)行更快速的方法，將暴力的算法復(fù)雜度從n的平方降低到nlgn 因此使用了歸并排序和二分查找   */void merge1(int num[],int p,int t,int q){    int temp[1000000];    int temp_index=0;    int i=t,j=q;    while(i>=p&&j>=t+1){        if(num[i]>=num[j]){            temp[temp_index++]=num[i--];        }else{            temp[temp_index++]=num[j--];        }    }//進(jìn)行局部排序        //對(duì)剩下的元素進(jìn)行處理    while(i>=p){        temp[temp_index++]=num[i--];    }    while(j>=t+1){        temp[temp_index++]=num[j--];    }    temp_index--;        //將結(jié)果賦給num數(shù)組    for(int i=p;i<=q;i++){        num[i]=temp[temp_index--];    }        }//歸并排序void merge_sort(int num[],int p,int q){    int t=0;    if(p<q){        t=(p+q)/2;//中間元素        merge_sort(num,p,t);        merge_sort(num,t+1,q);        merge1(num,p,t,q);//將拆分排序好的子序列進(jìn)行歸并    }}int main(){   // freopen("/Users/qigelaodadehongxiaodi/Desktop/data1.txt", "r", stdin);    //這個(gè)不理，是用來方便輸入輸出的東西，利用文本輸入流來讀取數(shù)據(jù)    //提交代碼的時(shí)候記得注銷這條語(yǔ)句        int t;    int s,n;    int num[1000008];    int flag;    scanf("%d",&t);    while(t>0){      //  PRintf("////zheli////n");        flag=0;        scanf("%d %d",&s,&n);        for(int i=0;i<n;i++){            scanf("%d",&num[i]);        }               merge_sort(num,0,n-1);//排序需要使用歸并排序或者堆排序，以達(dá)到nlgn的時(shí)間復(fù)雜度        //歸并排序＋二分搜索                                  int i=0,j=n-1;        while(i<j){            if((num[i]+num[j])<s){                i++;            }else                if((num[i]+num[j])>s){                    j--;                }else{                    printf("Yes/n");                    flag=1;                    break;                }        }                if(flag==0){            printf("No/n");        }        flag=0;                t--;    }    return 0;}
Output
對(duì)于每組數(shù)據(jù),如果存在滿足條件的2個(gè)數(shù),則輸出Yes,否則輸出No。
 
Sample Input
26 51 2 3 4 510 51 2 3 4 5
Sample Output
YesNo