首页 > 代码库 > PAT 1085 Perfect Sequence
PAT 1085 Perfect Sequence
PAT 1085 Perfect Sequence
题目：
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:10 82 3 20 4 5 1 6 7 8 9Sample Output:8地址：http://pat.zju.edu.cn/contests/pat-a-practise/1085
注意题意，说的是从数组中取任意多个数字满足完美子序列，所以对数字的要求没有顺序性。我的方法是，先对数组做一个排序，时间为O(nlogn)，然后在用线性的时间找到这个序列，如果该题用O(n^2)的算法则会有一个case超时。现在来说说如何在线性时间找到这个序列：首先，用下标i表示当前找到的最大值，用下标j表示当前找到的最小值。从j=0开始，i可以从0一直遍历到第一不满足data[0]*p >= data[i]，此时，说明序列0到i-1是满足完美子序列，也就是以data[0]为最小值的最大完美子序列，我们把其个数记为count；然后j加一，此时最小值变为data[1]，这是data[1]*p >= data[0]*p>=data[i]，也就是说原来的count个也都满足，但由于data[0]比data[1]要小，所以不满足data[1]为最小值，故count减一，然后在从当前的i开始往后继续找，找到第一个不满足data[1]*p>=data[i]，此时的count为以data[1]为最小值的最大完美子序列的个数，然后j继续加一，count减一，i继续向前遍历，如此循环直到j走到底。由于i,j在遍历时都没有回头，故时间复杂度为线性的。代码：
1 #include <stdio.h> 2 #include <algorithm> 3 using namespace std; 4 5 int main() 6 { 7 long long n,p; 8 long long data[100000]; 9 while(scanf("%lld%lld",&n,&p) != EOF){10 for(int i = 0; i < n; ++i){11 scanf("%lld",&data[i]);12 }13 sort(data,data+n);14 int result = 0;15 int count = 0;16 int i = 0, j = 0;17 long long sum;18 while(i < n){19 sum = data[j] * p;20 while(i < n && data[i] <= sum){21 ++count;22 ++i;23 }24 if(count > result)25 result = count;26 ++j;27 --count;28 29 }30 printf("%d\n",result);31 }32 return 0;33 }
PAT 1085 Perfect Sequence