1085. Perfect Sequence (25)

àì夳堔傛蜴生んèń 2022-05-29 14:16 235阅读 0赞

Given a sequence of positive integers and another positive integer p. The sequence is said to be a “perfect sequence” if M <= m * p where M and m are the maximum and minimum numbers in the sequence, respectively.

Now given a sequence and a parameter p, you are supposed to find from the sequence as many numbers as possible to form a perfect subsequence.

Input Specification:

Each input file contains one test case. For each case, the first line contains two positive integers N and p, where N (<= 105) is the number of integers in the sequence, and p (<= 109) is the parameter. In the second line there are N positive integers, each is no greater than 109.

Output Specification:

For each test case, print in one line the maximum number of integers that can be chosen to form a perfect subsequence.

Sample Input:

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

Sample Output:

  1. 8

题目大意:

代码:

  1. #include<stdio.h>
  2. #include<algorithm>
  3. using namespace std;
  4. long long a[100001],n;
  5. long long BinarySearch(long long start,long long end,long long key)
  6. {
  7. long long left=start,right=end;
  8. while(left<=right)
  9. {
  10. long long mind=left+(right-left)/2;
  11. if(a[mind]>key)
  12. {
  13. right=mind-1;
  14. }
  15. else if(a[mind]<key)
  16. {
  17. left=mind+1;
  18. }
  19. else
  20. {
  21. return mind;
  22. }
  23. }
  24. return left-1;
  25. }
  26. int main()
  27. {
  28. long long i,j,m,k,t,p;
  29. scanf("%lld %lld",&n,&p);
  30. for(i=0;i<n;i++)
  31. {
  32. scanf("%lld",&a[i]);
  33. }
  34. sort(a,a+n);
  35. k=0;
  36. for(i=0;i<n;i++)
  37. {
  38. m=a[i]*p;//int 会越界,所以用 long long(不然最后一个case通不过)
  39. t=BinarySearch(i,n-1,m);
  40. if(k<t-i+1)
  41. {
  42. k=t-i+1;
  43. }
  44. }
  45. printf("%lld\n",k);
  46. return 0;
  47. }

发表评论

表情:
评论列表 (有 0 条评论,235人围观)

还没有评论,来说两句吧...

相关阅读

    相关 1085. PAT单位排行 (25)

    每次 PAT 考试结束后,考试中心都会发布一个考生单位排行榜。本题就请你实现这个功能。 输入格式: 输入第一行给出一个正整数N(<=105),即考生人数。随后N行,每行按下

    相关 bzoj 1085骑士精神

    bzoj 1085骑士精神 在一个5×5的棋盘上有12个白色的骑士和12个黑色的骑士,且有一个空位。在任何时候一个骑士都能按照骑士的走法(它可以走到和它横坐标相差为1,纵坐标