3624 - 完美序列
给定一串正整数序列和一个正整数p.如果M<=m*p(M为该序列最大数,m为该序列最小数)则该序列为完美序列.
现给一串序列和p,你需要从这串序列拿出其中数字组成最长的完美序列.
题目输入
第一行含2个正整数N,p.N(N<=105)为该序列的长度,p(p<=109).
第二行为N个正整数(每个数最大为109).
题目输出
输出最大完美序列的长度.
输入/输出样例
题目输入
10 8 2 3 20 4 5 1 6 7 8 9
题目输出
8
C语言解答
#include<stdio.h> int main() { int n,p,max,i,j,x[112],t; while(scanf("%d%d",&n,&p)==2) { max=0; for(i=0;i<n;i++) scanf("%d",&x[i]); for(i=0;i<n-1;i++) for(j=i+1;j<n;j++) if(x[i]>x[j]){t=x[i];x[i]=x[j];x[j]=t;} for(i=0;i<n;i++) { for(j=n-1;j>i;j--) if(x[i]*p>=x[j])break; t=j-i+1;if(t>max)max=t; } printf("%d\n",max); } return 0; }
C++解答
#include<string.h> #include<stdio.h> #include<stdlib.h> #include<iostream> #include<vector> #include<algorithm> using namespace std; typedef long long ll; int main(){ vector<int>vec; int n,p,i,ans,tmp,x; long long xx; while(scanf("%d%d",&n,&p)!=EOF){ vec.clear(); ans=0; for(i=0;i<n;i++){ scanf("%d",&x); vec.push_back(x); } sort(vec.begin(),vec.end()); for(i=0;i<n;i++){ xx=(long long)((long long)vec[i]*(long long)p); int maxpos; if(xx>1000000000) maxpos=n-1; else maxpos=upper_bound(vec.begin(),vec.end(),(int)xx)-vec.begin()-1; tmp=maxpos-i+1; if(ans<tmp){ ans=tmp; } } printf("%d\n",ans); } return 0; }