1085. Perfect Sequence (25)

时间限制 300 ms 内存限制 65536 kB 代码长度限制 16000 B 判题程序 Standard 作者 CAO, Peng

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 (<= 10⁵) is the number of integers in the sequence, and p (<= 10⁹) is the parameter. In the second line there are N positive integers, each is no greater than 10⁹.

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: 10 8 2 3 20 4 5 1 6 7 8 9 Sample Output: 8

---

提交代码

 

1 #include<cstdio> 2 #include<stack> 3 #include<algorithm> 4 #include<iostream> 5 #include<stack> 6 #include<set> 7 #include<map> 8 #include<vector> 9 using namespace std; 10 long long line[100005]; 11 int main(){ 12 //freopen("D:\\INPUT.txt","r",stdin); 13 long long n,p; 14 scanf("%lld %lld",&n,&p); 15 int i,j; 16 for(i=0;i<n;i++){ 17 scanf("%lld",&line[i]); 18 } 19 sort(line,line+n); 20 int amount; 21 long long cur=line[0]*p; 22 for(j=0;j<n&&line[j]<=cur;j++);//j指针 23 amount=j; 24 for(i=1;i<n&&j<n;i++){//这里的j<n是为了避免不必要的循环 25 cur=line[i]*p; 26 for(;j<n&&line[j]<=cur;j++); 27 if(j-i>amount){ 28 amount=j-i; 29 } 30 } 31 printf("%d\n",amount); 32 return 0; 33 }

 

转载于:https://www.cnblogs.com/Deribs4/p/4784082.html

总结

以上是生活随笔为你收集整理的pat1085. Perfect Sequence (25)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。