[PAT解题报告] Perfect Sequence
不太难，我出的题……
给定一个正整数序列，再给一个正整数p, 选出最多选出多少个数，使得最小值不超过最大值的p倍？
因为只考虑最小值和最大值，所以可以把原数列排序。
假设数组a[]都排好序了。
我们对起点i，循环找到最后一个满足条件的位置j >= i。
当i + 1的时候，注意j仍然有效，因为a[j] <= p * a[i] <= p * a[i +
1]，所以j没必要重新循环，而是从上一次的最后一个位置继续向后找就行了。
所以不算排序的话，对每个i找到j的时间复杂度是O(n)的，因为i, j都只循环了n次而已。
另外注意，判断p倍可能超int，所以建议用除法（上取整）来判断倍数关系。
代码：
#include <cstdio>
#include <algorithm>
using namespace std;
int a[100006];
int main() {
int answer = 1, m ,n ;
scanf("%d%d",&n,&m);
for (int i = 0;i < n; ++i) {
scanf("%d",a + i);
}
sort(a, a + n);
for (int i = 0, j = 0; (i < n) && (j < n); ++i) {
for (; (j < n) && ((a[j] + a[i] - 1) / a[i] <= m); ++j)
;
answer = max(answer, j - i);
}
printf("%d\n",answer);
return 0;
}
原题链接： http://www.patest.cn/contests/pat-a-practise/1085
360集团公司福利 395人发布