PAT-B 1030. 完美数列(25)

传送门

https://www.patest.cn/contests/pat-b-practise/1030

题目

给定一个正整数数列,和正整数p,设这个数列中的最大值是M,最小值是m,如果M <= m * p,则称这个数列是完美数列。
现在给定参数p和一些正整数,请你从中选择尽可能多的数构成一个完美数列。
输入格式:
输入第一行给出两个正整数N和p,其中N(<= 105)是输入的正整数的个数,p(<= 109)是给定的参数。第二行给出N个正整数,每个数不超过109。
输出格式:
在一行中输出最多可以选择多少个数可以用它们组成一个完美数列。
输入样例:
10 8
2 3 20 4 5 1 6 7 8 9
输出样例:
8

分析

1.首先将数字都读进数组里,然后用sort或者qsort排序(升序),都可以
2.接着就是比较绕的一个地方了,这里我的第一种方法的时间复杂度是m * n,然后有一个测试点超时了,考虑了一下是算法太麻烦。

这里给大家介绍一种很快速的算法,以本题样例为例:
对其排序后,是这样的:

下标:|00|01|02|03|04|05|06|07|08|09|
数值:|01|02|03|04|05|06|07|08|09|20|

1.首先用1 * 8 = 8,然后会对比到下标为7 的位置,并记长度为8。
2.接着就厉害了,按我之前的做法是从下标为01的地方对比,这样就麻烦了。
快速的做法是计算2 * 8 = 16,然后用下标为08的地方与其对比,发现符合,然后求出从下标01到08位置的长度,是8,不大于之前的长度,接着向后对比;用下标为09的数值与2 * 8 = 16对比,发现不符合规则,然后此次对比过程结束。
3.新的最大值是3 * 8 = 21,用下标为09的地方与其对比,发现符合,然后求从下标02到09的长度,是8,不大于之前的长度,并且发现已经全部对比完毕,所以结束。

源代码

//C/C++实现
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    int n;
    long long p;
    scanf("%d %d", &n, &p);
    vector<int> v(n);
    for(int i = 0; i < n; ++i){
        scanf("%d", &v[i]);
    }
    sort(v.begin(), v.end());
    int final_count = 0;
    for(int i = 0; i < n; ++i){
        long long max = v[i] * p;
        for(int j = i + final_count; j < n; ++j){
            if(v[j] <= max){
                if(j - i + 1 > final_count){
                    final_count = j - i + 1; //从j到i的数值的数量
                }
            }
            else{
                break;
            }
        }
    }
    printf("%d\n", final_count);
    return 0;
}

当前网速较慢或者你使用的浏览器不支持博客特定功能,请尝试刷新或换用Chrome、Firefox等现代浏览器