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

Sample Output:

8

주소:http://pat.zju.edu.cn/contests/pat-a-practise/1085
수조에서 임의의 여러 개의 숫자를 추출하여 완벽한 서열을 충족시키기 때문에 숫자에 대한 요구는 순서가 없다는 뜻에 주의하십시오.나의 방법은 먼저 수조에 대해 정렬을 하고 시간은 O (nlogn) 이다. 그리고 선형적인 시간에 이 서열을 찾는 것이다. 만약 이 문제가 O (n^2) 알고리즘을 사용한다면 케이스가 시간을 초과할 것이다.현재 온라인 시간에 이 서열을 어떻게 찾는지 말합니다. 우선, 현재 찾은 최대 값을 아래에 표시한 i로 표시하고, 아래에 표시한 j로 현재 찾은 최소 값을 표시합니다.j=0부터 i는 0에서 1까지 데이터[0]*p>=데이터[i]를 충족시키지 못하도록 두루 돌아다닐 수 있다. 이때 서열 0에서 i-1은 완벽한 서열을 충족시키는 것이다. 즉, 데이터[0]를 최소값으로 하는 최대 완벽한 서열이고 우리는 그 개수를count로 기록한다.그리고 j에 하나를 더하면 이때 최소치가 데이터[1]로 바뀐다. 이것은 데이터[1]*p>=데이터[0]*p>=데이터[i]이다. 즉, 원래의count개도 모두 만족하지만 데이터[0]보다 작기 때문에 데이터[1]를 최소치로 만족시키지 못하기 때문에count를 하나 줄인 다음에 현재의 i부터 계속 찾아서 첫 번째는 데이터[1]*p>=데이터[i]를 찾는다. 이때의count는데이터[1]를 최소치로 하는 최대 완벽한 서열의 개수로 한다.그리고 j는 계속 1을 더하고count는 1을 줄이고 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
",result); 31  } 32     return 0; 33 }