PAT乙级1030-一一网

题目

给定一个正整数数列，和正整数 p，设这个数列中的最大值是 M，最小值是 m，如果 M≤mp，则称这个数列是完美数列。
现在给定参数 p 和一些正整数，请你从中选择尽可能多的数构成一个完美数列。

输入格式：

输入第一行给出两个正整数 N 和 p，其中 10^5）是输入的正整数的个数，p（≤10
^9）是给定的参数。第二行给出 N 个正整数，每个数不超过 10^9 。

输出格式：

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

样例就不放了。感兴趣自己去官网看看。

思路

这是我乙级目前做的最莫名其妙的题了。先开始用开一个10000的数组总是超时，转化为vector就过了，再回来改一下数组的又过了。总之很离谱。

先将数据全部存入数组或者vector容器中，差别不大。在用sort进行从小到大的排序。最后进行两个嵌套循环。注意第二个循环的条件起始值j为i+maxx(maxx是目前的最大完美数列个数)。毕竟你找的完美序列个数比maxx小就能没用，徒劳占据运行时间。循环内进行判定(v[j] <= v[i] * p若不满足直接跳出循环，v[j]只会越来越大，不会满足这个条件的，优化成功！

//foreverking
// 给定一个正整数数列，和正整数 p，设这个数列中的最大值是 M，最小值是 m，如果 M≤mp，则称这个数列是完美数列。
#include <vector>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cmath>
using namespace std;

int n;
long long p;
int res,maxx;

// int main(){
//     scanf("%d%lld", &n, &p);
//     //cin >> n >> p;
//     for(int i = 0; i < n; i++){
//         //代码
//         cin >> s[i];
//         }
//     //先排序
//     sort(s,s + n);//从小到大

//     for(int i = 0; i < n; i++){
//         //int minn = s[i];//将此数当作最小数
        
//         for(int j = n - 1; j >= i + maxx; j--){
//             if(s[j] <= s[i] * p)
//                 res = j - i + 1;//ji之间的元素
//                 if(res > maxx)
//                     maxx = res;
//         }
//     }

//     printf("%d\n",maxx);
//     return 0;
// }

int main(){
    cin >> n >> p;
    vector<int> v(n);//有n个元素的vector容器
    for(int i = 0; i < n; i++){
        cin >> v[i];
        }
    //先排序
    /*
    !也可以这样输入
    vector<int> v;
	for (int i = 0; i < n; i++)
	{
		int c;
		cin >> c;
		v.push_back(c);
		}
    */
    sort(v.begin(),v.end());//从小到大

    for(int i = 0; i < n; i++){
        //int minn = s[i];//将此数当作最小数
        
        for(int j = i + maxx; j < n; j++){//小于暂时的maxx
            if(v[j] <= v[i] * p){
                res = j - i + 1;//ji之间的元素
                if(res > maxx)
                    maxx = res;
            }
            else
                break;//v[j]变得更大了，不可能满足v[j] <= v[i] * p
        }
    }

    printf("%d\n",maxx);
    return 0;
}
复制代码

这就过了。回过头看数组，一样的思路，只是用数组存数据。

//foreverking
// 给定一个正整数数列，和正整数 p，设这个数列中的最大值是 M，最小值是 m，如果 M≤mp，则称这个数列是完美数列。
#include <vector>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cmath>
using namespace std;

const int N = 1e5;

int n;
long long p;
int s[N];
int res,maxx;

int main(){
    scanf("%d%lld", &n, &p);
    //cin >> n >> p;
    for(int i = 0; i < n; i++){
        //代码
        cin >> s[i];
        }
    //先排序
    sort(s,s + n);//从小到大

    for(int i = 0; i < n; i++){
        //int minn = s[i];//将此数当作最小数
        
        for(int j = i + maxx; j < n; j++){
            if(s[j] <= s[i] * p){
                res = j - i + 1;//ji之间的元素
                if(res > maxx)
                    maxx = res;
            }
                else
                    break;
                    
        }
    }

    printf("%d\n",maxx);
    return 0;
}
复制代码