1001: 好像很简单的

Description

给出一个整数S,另外给出n个数,判断是否可以从中取出2个数,使得这两个数的和是S。

Input

第一行有个整数T(1 <= T <= 30),代表数据组数。

对于每组数据,第一行包含两个整数S(1 <= S <= 1000000)，n(1 <= n <= 100000)。第二行包含n个整数，整数的范围为[1,1000000]。

#include "stdio.h"#include "stdlib.h"#include "math.h"/*  思路：本题其实就是使用暴力破解的方式，但是我们会发现超时 因此要进行更快速的方法，将暴力的算法复杂度从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--];        }    }//进行局部排序        //对剩下的元素进行处理    while(i>=p){        temp[temp_index++]=num[i--];    }    while(j>=t+1){        temp[temp_index++]=num[j--];    }    temp_index--;        //将结果赋给num数组    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);//将拆分排序好的子序列进行归并    }}int main(){   // freopen("/Users/qigelaodadehongxiaodi/Desktop/data1.txt", "r", stdin);    //这个不理，是用来方便输入输出的东西，利用文本输入流来读取数据    //提交代码的时候记得注销这条语句        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);//排序需要使用归并排序或者堆排序，以达到nlgn的时间复杂度        //归并排序＋二分搜索                                  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
对于每组数据,如果存在满足条件的2个数,则输出Yes,否则输出No。
 
Sample Input
26 51 2 3 4 510 51 2 3 4 5
Sample Output
YesNo