【PAT甲级真题】- Perfect Sequence (25)

题目来源Perfect Sequence (25)题目描述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 possibleto form a perfect subsequence.输入描述: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 Npositive integers, each is no greater than 109.输出描述:For each test case, print in one line the maximum number of integers that can be chosen to form a perfect subsequence.输入例子:10 8 2 3 20 4 5 1 6 7 8 9输出例子:8思路简介这种对最大最小有要求的题目首先想到双指针一开始想两头双指针然后发现好像没什么意义然后就想着从同一头出发发现是可行的首先要排序然后初始两个指针都指向最左点开始遍历如果满足条件更新最大值同时说明最大值可能可以更大右指针右移如果不满足条件只能移动左指针看看后续能不能扩大序列注意循环的条件是左右指针不能越界且左指针不能超过右指针虽然理论上是不可能超的遇到的问题无一遍过代码/** * https://www.nowcoder.com/pat/5/problem/4035 * 双指针 */#includebits/stdc.husingnamespacestd;voidsolve(){intn,p;cinnp;vectorintv(n);for(inti0;in;i)cinv[i];sort(v.begin(),v.end());intlenv.size();intl0,r0,mx0;while(rlenllenlr){if(v[l]*p-v[r]0){//说明不够大可以移动右指针mxmax(mx,r-l1);r;}else{//说明太大了得移动左指针l;}}coutmx;}intmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);//fstream in(in.txt,ios::in);cin.rdbuf(in.rdbuf());intT1;//cinT;while(T--){solve();}return0;}