二分搜索降低时间复杂度
1
2
3
4
5
6
| int main(){
cin >> n >> m;
for(int i=0;i<n;i++) cin >> s[i];
canFit();
return 0;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| #include <iostream>
#include <algorithm>
#define MAXN 150
using namespace std;
int n,m,s[MAXN];
int ss[MAXN];
bool canFit(){
int flag = 0;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
for(int k=0;k<n;k++)
for(int l=0;l<n;l++)
if( s[i] + s[j] + s[l] + s[k] == m) flag = true;
if(flag) cout << "YES";
else cout << "NO" ;
}
|
时间复杂度为O(n^4),只能在n较小的情况下,若n较大,则TLE…
时间复杂度为O(n^3log2(n))的做法:一层二分搜索
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| #include <iostream>
#include <algorithm>
#define MAXN 150
using namespace std;
int n,m,s[MAXN];
int ss[MAXN];
bool binSearch(int k){
int r=n,l=0;
while(l <= r){
int i = (r+l)/2;
if ( s[i] == k) return true;
else if( s[i] < k) l = i+1;
else r= i-1;
}
return false;
}
bool canFit(){
int flag = 0;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if( binSearch(m-s[i] - s[j] - s[k]) flag = true;
if(flag) cout << "YES";
else cout << "NO" ;
}
|
O(n^2log2(n))做法: 排序O(n^2log2(n)),循环O(n^2log2(n)),总共也是O(n^2log2(n))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| #include <iostream>
#include <algorithm>
#define MAXN 150
using namespace std;
int n,m,s[MAXN];
int ss[MAXN];
bool binSearch(int k){
int l=0,r=n*n;
while(l <= r){
int i = (r+l)/2;
if ( s[i] == k) return true;
else if( s[i] < k) l = i+1;
else r= i-1;
}
return false;
}
void enumeration(){
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
ss[i*n+j] = s[i] + s[j];
}
bool canFit(){
enumeration();
sort(ss,ss+n*n);
int flag = 0;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if( binSearch(m- s[i] - s[j] )) flag = true;
if(flag) cout << "YES";
else cout << "NO" ;
}
|
▲需要注意的是,ss[n*n]的数组需要先排序才能使用二分搜索
----出自:<<挑战程序设计竞赛>>
