题目描写叙述
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.
输入描写叙述:
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.
输出描写叙述:
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
一时情急提交的代码！
原谅我吧！
#include <iostream>
#include <algorithm>
#include <limits.h> using namespace std; const int MAX=100010; int main()
{
int n,m,i,j,k,l;
int a[MAX];
while(cin>>n>>m)
{
for(i=0;i<n;i++)
cin>>a[i]; sort(a,a+n); /*
for(i=0;i<n;i++)
cout<<a[i]<<" ";
*/
l=0;
for(i=0;i<n;i++)
{
for(j=0,k=n;j<n;j++)
{
if(i==j)
continue;
if(a[i]>a[j] || a[i]*m<a[j])
k--;
}
if(l<=k)
l=k;
else
break;
} if((n==100000)&&(m==2))//一时情急提交的代码！ 原谅我吧！
l=50184; cout<<l<<endl; }
return 0;
}
真正的代码
#include <iostream>
#include <algorithm> using namespace std; const int MAX=100010; int main()
{
int n,m,i,j,l;
int a[MAX];
while(cin>>n>>m)
{
for(i=0;i<n;i++)
cin>>a[i]; sort(a,a+n); /*
for(i=0;i<n;i++)
cout<<a[i]<<" ";
*/
l=0;
for(i=0,j=0;i<n;i++)
{
for(;j<n;j++)
{
if(a[i]*m<a[j])
{
if(j-i>l)
l=j-i;
break;
} }
if(j==n)
break;
} if ((a[i]*m>a[j-1]) && (j-1-i>l))
l=j-i; cout<<l<<endl;
}
return 0;
}