PTA A_1085 Perfect Sequence

798236606

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

解：
1.二分法

#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long int LL;

int a[100010];

int main()
{
    int n, p;
        
    scanf("%d %d", &n, &p);
        
    for (int i = 0; i < n; i++)
        scanf("%d", a + i);
                
    sort(a, a + n);
    
    int maxlen = 0;        
    for (int i = 0; i < n; i++)
    {
        LL limit = (LL)a[i] * (LL)p;
        int pa = upper_bound(a + i, a + n, limit) - a - i;

        if (pa > maxlen)
            maxlen = pa;
    }
        
    printf("%d", maxlen);
        
    return 0;
}

2.two pointers

#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long int LL;

int a[100010];

int main(void)
{
        int n, p;
        
        scanf("%d %d", &n, &p);
        
        for (int i = 0; i < n; i++)
                scanf("%d", a + i);
                
        sort(a, a + n);

        int i = 0, j = 0, maxlen = 1;
        
        for (i = 0; i < n; i++)
        {
                LL limits = (LL)a[i] * (LL)p;
                
                while (j < n && a[j] <= limits)
                        j++;

                maxlen = max(j - i, maxlen);
        }
        
        printf("%d", maxlen);
        
        return 0;
}