Dowemo
0 0 0 0

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