分析
有两种方法:二分法、尺取法(即双指针法)
复杂度:均为$O(NlogN)$
方法1
:二分法
直接使用STL库
的做法:
前置知识:语句upper_bound(a+l+1,a+1+r,k)-lower_bound(a+l+1,a+1+r,k)
的值意为数组[l,r]
键值为k
的个数
代码:
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int a[N];
int n,m;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+1+n);
bool ok=0;
for(int i=1;i<=n;i++){
int k=m-a[i];
if(upper_bound(a+i+1,a+1+n,k)-lower_bound(a+i+1,a+1+n,k)){
ok=1;
cout<<a[i]<<' '<<k;
break;
}
}
if(!ok) cout<<"No Solution"<<endl;
return 0;
}
手写二分:
代码:
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int a[N];
int n,m;
bool check(int k,int pos){
int l=pos,r=n;
while(l<r){
int mid=l+r>>1;
if(a[mid]==k) return true;
else if(a[mid]<k) l=mid+1;
else if(a[mid]>k) r=mid;
}
return a[l]==k;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+1+n);
bool ok=0;
for(int i=1;i<=n-1;i++){
int k=m-a[i];
if(check(k,i+1)){
ok=1;
cout<<a[i]<<' '<<k;
break;
}
}
if(!ok) cout<<"No Solution"<<endl;
return 0;
}
尺取法:
首先要排序维护单调的关系。
令变量s,t
分别指向数组首尾,如果a[s]+a[t]==m
则为找到目标解,输出即可;
如果a[s]+a[t]<m
,s
右移使得a[s]+a[t]
增大;
反之t
左移。
代码:
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int a[N];
int n,m;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
//特判n=1
if(n==1){
cout<<"No Solution";
return 0;
}
sort(a+1,a+1+n);
int s=1,t=n;
bool ok=0;
while(s!=t){
if(a[s]+a[t]==m){
cout<<a[s]<<' '<<a[t]<<endl;
ok=1;
break;
}
else if(a[s]+a[t]<m) s++;
else if(a[s]+a[t]>m) t--;
}
if(!ok) cout<<"No Solution";
return 0;
}
二分会比尺取要快些吧
似乎并非如此:
我的评测结果是:
STL二分
284ms
手写二分
205ms
尺取
182ms
除开
sort
的过程,二分还是需要$O(NlogN)$ ,而尺取是$O(N)$%