PTA A_1085 Perfect Sequence

798236606

题目链接：https://pintia.cn/problem-sets/994805342720868352/problems/994805381845336064

解：
1.二分法

1. #include <cstdio>
   
2. #include <algorithm>
   
3. 
   
4. using namespace std;
   
5. 
   
6. typedef long long int LL;
   
7. 
   
8. int a[100010];
   
9. 
   
10. int main()
    
11. {
    
12.     int n, p;
    
13.         
    
14.     scanf("%d %d", &n, &p);
    
15.         
    
16.     for (int i = 0; i < n; i++)
    
17.         scanf("%d", a + i);
    
18.                
    
19.     sort(a, a + n);
    
20.    
    
21.     int maxlen = 0;        
    
22.     for (int i = 0; i < n; i++)
    
23.     {
    
24.         LL limit = (LL)a[i] * (LL)p;
    
25.         int pa = upper_bound(a + i, a + n, limit) - a - i;
    
26. 
    
27.         if (pa > maxlen)
    
28.             maxlen = pa;
    
29.     }
    
30.         
    
31.     printf("%d", maxlen);
    
32.         
    
33.     return 0;
    
34. }

复制代码

2.two pointers

1. #include <cstdio>
   
2. #include <algorithm>
   
3. 
   
4. using namespace std;
   
5. 
   
6. typedef long long int LL;
   
7. 
   
8. int a[100010];
   
9. 
   
10. int main(void)
    
11. {
    
12.         int n, p;
    
13.         
    
14.         scanf("%d %d", &n, &p);
    
15.         
    
16.         for (int i = 0; i < n; i++)
    
17.                 scanf("%d", a + i);
    
18.                
    
19.         sort(a, a + n);
    
20. 
    
21.         int i = 0, j = 0, maxlen = 1;
    
22.         
    
23.         for (i = 0; i < n; i++)
    
24.         {
    
25.                 LL limits = (LL)a[i] * (LL)p;
    
26.                
    
27.                 while (j < n && a[j] <= limits)
    
28.                         j++;
    
29. 
    
30.                 maxlen = max(j - i, maxlen);
    
31.         }
    
32.         
    
33.         printf("%d", maxlen);
    
34.         
    
35.         return 0;
    
36. }

复制代码