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 }
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.