PAT乙级1030

2017-01-13 08:17:59来源:CSDN作者:qq_22194315人点击

第七城市

1030. 完美数列(25)

时间限制300 ms
内存限制65536 kB
代码长度限制8000 B
判题程序Standard作者CAO, Peng

给定一个正整数数列,和正整数p,设这个数列中的最大值是M,最小值是m,如果M <= m * p,则称这个数列是完美数列。

现在给定参数p和一些正整数,请你从中选择尽可能多的数构成一个完美数列。

输入格式:

输入第一行给出两个正整数N和p,其中N(<= 105)是输入的正整数的个数,p(<= 109)是给定的参数。第二行给出N个正整数,每个数不超过109

输出格式:

在一行中输出最多可以选择多少个数可以用它们组成一个完美数列。

输入样例:
10 82 3 20 4 5 1 6 7 8 9
输出样例:

8

#include<stdio.h>#include<iostream>#include<algorithm>#include<set>#include<string>#include<vector>using namespace std;int main(){	int N;long long p;	cin >> N >> p; vector<long long> v;	long long temp;	while (N--)	{		cin >> temp;		v.push_back(temp);	}	sort(v.begin(), v.end());	/*int i, j;	i = 0;	j = v.size() - 1;//双指针法	while(i<j)	{		if (v[i] * p >= v[j])			break;		else		{			i++;			if (v[i] * p >= v[j])				break;			else			{				i--;				j--;				if (v[i] * p >= v[j])					break;				else				{					i++;				}			}		}	}	int k;	for (k = 0; k <= j; k++)	{		if (v[k] * p >= v[j])			break;	}	int k1;	for (k1 = v.size()-1; k1>=i; k1--)	{		if (v[i] * p >= v[k1])			break;	}	if (i >= j)	{		cout << 1;	}	else		cout << max(j - k + 1,k1-i+1);		这种方法会扣两分*/	/*int maxNumbers = -1; int oldj=-1;	for (int i = 0; i < v.size(); i++)	{		for (int j = v.size()-1; j>=i; j--)		{			if (j <= oldj)					break;			if (v[i] * p >= v[j])			{								if (maxNumbers < j - i + 1)				{					maxNumbers = j - i + 1;					oldj = j;				}				break;			}		}	}	cout << maxNumbers;	有一个点会超时,扣三分*/	int max = 0;	for (int i = 0; i < v.size(); i++)	{		for (int j = i+max; j < v.size(); j++)//这个地方有个trick,必须利用上一次所得到的max		{									//来去掉没必要的遍历,这题想了很久。。。			if (v[i] * p >= v[j])			{				if (max < j - i + 1)				{					max = j - i + 1;				}			}			else				break;		}	}	cout << max;	return 0;}


第七城市

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台