Dowemo

A 1001 array and equal to k in an array of Baseline time limit: 1 seconds space limit: 131072 kb score: 5 difficulty: algorithm Collect Focus on giving an integer k and an unordered array a, an element of an n is n independent integers, and finding out all and equal to k in array a. For example k = 8, array a: A % 7b-1, 6, 5, 3, 4, 2, microformats, 0, 8,,,, ( -1 ), ( 0 ), ( ), ( ), ( 3 ), ( ), ( ), ( ), ( ), ( ), ( ), (, 6 ), ( ), ( ), ( ), ( ), ( ), ( ), ( ), ( ), (, ), ( ), ( ), ( ), ( ), ( ), ( ), (, ), ( ), ( ), ( ), ( ), (, ), ( ), ( ), ( ), ( ), (, ), ( ), ( ), ( ), ( ), ( ), ( ), ( ), ( ), ( ), ( ), ( ), ( ), ( ), ( ), ( ). Input

第1行:用空格隔开的2个数,K N,N为A数组的长度。(2 <= N <= 50000,-10^9 <= K <= 10^9)


第2 - N + 1行:A数组的N个元素。(-10^9 <= A[i] <= 10^9) 





Output

第1 - M行:每行2个数,要求较小的数在前面,并且这M个数对按照较小的数升序排列。


如果不存在任何一组解则输出:No Solution。





Input example

8 9


-1


6


5


3


4


2


9


0


8





Output example

-1 9


0 8


2 6


3 5








chinese

Idea: to find the addition of k, the idea of this dish is to sort first and then use binary to find the other half of it, and mark the data.

( it looks like no binary search, but it's better to improve efficiency ).




#include <iostream>


#include<cstdio>


#include<string.h>


#include<algorithm>


using namespace std;


const int maxn=5e4+10;


int k,n;


int a[maxn],b[maxn];


int tmp;


//采用二分搜索解决


bool solve(int i)


{


 int lb=-1,ub=n;


 while(ub-lb>1)


 {


 int mid=(lb+ub)/2;


 if(a[mid]+i>k)


 {


 ub=mid;


 }


 else if(a[mid]+i<k)


 {


 lb=mid;


 }


 else if(a[mid]+i==k)


 {



 b[mid]=1;


 tmp=a[mid];


 return true;


 }


 }


 return false;


}


int main()


{


 cin>>k>>n;


 int flag=0;


 for(int i=0;i<n;i++)


 {


 cin>>a[i];



 }


 sort(a,a+n);


 for(int i=0;i<n;i++)


 {


 if(b[i]==0&&solve(a[i]))


 {


 if(a[i]==tmp)continue;


 flag=1;


 cout<<a[i]<<""<<tmp<<endl;


 }


 }


 if(flag==0)cout<<"No Solution"<<endl;


 return 0;


}

















Copyright © 2011 Dowemo All rights reserved.    Creative Commons   AboutUs