798236606 发表于 2020-1-29 11:30:12

PTA A_1085 Perfect Sequence

本帖最后由 798236606 于 2020-1-29 15:32 编辑

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

解：
1.二分法
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long int LL;

int a;

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 * (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;

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 * (LL)p;
               
                while (j < n && a <= limits)
                        j++;

                maxlen = max(j - i, maxlen);
      }
      
      printf("%d", maxlen);
      
      return 0;
}
页: [1]
查看完整版本: PTA A_1085 Perfect Sequence