【算法笔记】B1030 完美数列（三种方法）

1030 完美数列（25 分)

给定一个正整数数列，和正整数

现在给定参数

输入格式：

输入第一行给出两个正整数

输出格式：

在一行中输出最多可以选择多少个数可以用它们组成一个完美数列。

输入样例：

10 8
2 3 20 4 5 1 6 7 8 9

输出样例：

思路：

所有完美数列应该都是在数组的递增序列上的连续若干个数，所以应该先对数组排序，然后再寻找最大的完美数列。

codes

暴力版：

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 const int maxn = 100010;
 5 
 6 int main(){
 7     long long n, p, num[maxn];
 8     cin>>n>>p;
 9     for(int i = 0; i < n; i++) cin>>num[i];
10     sort(num, num + n);
11     int cnt = 0;
12     for(int i = 0; i < n; i++){
13         for(int j = i + cnt; j < n; j++){
14             if(num[j] > num[i] * p) break;
15             if(j-i+1>cnt) cnt=j-i+1;
16         }
17     }
18     cout<<cnt;
19     return 0;
20 }

二分法：

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 const int maxn = 100010;
 5 long long n,p,a[maxn];
 6 int binarySearch(int i, long long x){
 7     if(a[n-1] <= x) return n;
 8     int l = i + 1, r = n - 1 , mid;
 9     while(l < r){
10         mid = (l + r) / 2;
11         if(a[mid] <= x) l = mid + 1;
12         else r = mid;
13     }
14     return l;
15 }
16 int main(){
17     cin>>n>>p;
18     for(int i = 0; i < n; i++){
19         cin>>a[i];
20     }
21     sort(a, a + n);
22     int ans = 1;
23     for(int i = 0; i < n; i++){
24         int j = binarySearch(i, a[i]*p);
25         if(j - i > ans) ans = j - i;
26     }
27     cout<<ans;
28     return 0;
29 }

双指针：

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 const int maxn = 100010;
 5 long long n,p,a[maxn];
 6 
 7 int main(){
 8     long long n,p,a[maxn];
 9     cin>>n>>p;
10     for(int i=0;i<n;i++) cin>>a[i];
11     sort(a,a+n);
12     int ans=1,i=0,j=0;
13     while(i<n&&j<n){
14         while(j<n && a[j]<=a[i]*p){
15             if(j-i+1>ans) ans = j-i+1;
16             j++;
17         }
18         i++;
19     }
20      cout<<ans;
21     return 0;
22 }