The title

Given a sequence of positive integers, and p, let the maximum value in the sequence be M and the minimum value be M. If M≤mp, the sequence is said to be perfect. Now, given p and some positive integers, choose as many of them as possible to form a perfect sequence.

Input format:

The first line of the input gives two positive integers N and p, where 10^5) is the number of positive integers in the input and p (≤10 ^9) is the given parameter. The second line gives N positive integers, each not exceeding 10 to the ninth.

Output format:

How many numbers can you print in a row to form a perfect sequence.

I’m not going to show you the sample. If you are interested, go to the official website.

Train of thought

This is the most baffling problem I’ve ever done in grade B. If you start with an array of 10000, it always times out. If you start with an array of 10000, it always times out. If you turn it into a vector, it always times out. Anyway, it’s crazy.

Start by storing all the data in an array or vector. It doesn’t make much difference. Sort from smallest to largest using sort. Finally, two nested loops are performed. Note that the conditional starting value j for the second loop is I +maxx(maxx is the current maximum number of perfect sequences). After all, the number of perfect sequences you’re looking for is smaller than maxx, and it’s useless to take up running time. Cycle to determine (v[j] <= v[I] * p if not meet the direct jump out of the cycle, V [j] will only be more and more large, will not meet this condition, optimization success!

//foreverking
// Given a sequence of positive integers, and a positive integer p, let the maximum value of the sequence be M, the minimum value of the sequence be M, if M≤mp, then the sequence is said to be perfect.
#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++){
/ / / / code
// cin >> s[i];
/ /}
// // sort first
// sort(s,s + n); // From small to big

// for(int i = 0; i < n; i++){
// //int minn = s[i]; // take this number as the minimum
        
// for(int j = n - 1; j >= i + maxx; j--){
// if(s[j] <= s[i] * p)
// res = j - i + 1; // Elements between ji
// if(res > maxx)
// maxx = res;
/ /}
/ /}

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

int main(){
    cin >> n >> p;
    vector<int> v(n);// A vector with n elements
    for(int i = 0; i < n; i++){
        cin >> v[i];
        }
    / / first order
    / *! Vector 
      
        v; for (int i = 0; i < n; i++) { int c; cin >> c; v.push_back(c); } * /
      
    sort(v.begin(),v.end());// From small to big

    for(int i = 0; i < n; i++){
        //int minn = s[i]; // take this number as the minimum
        
        for(int j = i + maxx; j < n; j++){// Less than temporary maxx
            if(v[j] <= v[i] * p){
                res = j - i + 1;// Elements between ji
                if(res > maxx)
                    maxx = res;
            }
            else
                break;//v[j] becomes larger and cannot satisfy v[j] <= v[I] * p
        }
    }

    printf("%d\n",maxx);
    return 0;
}
Copy the code

That’s over. If we go back to arrays, we have the same idea, but arrays hold data.

//foreverking
// Given a sequence of positive integers, and a positive integer p, let the maximum value of the sequence be M, the minimum value of the sequence be M, if M≤mp, then the sequence is said to be perfect.
#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++){
        / / code
        cin >> s[i];
        }
    / / first order
    sort(s,s + n);// From small to big

    for(int i = 0; i < n; i++){
        //int minn = s[i]; // take this number as the minimum
        
        for(int j = i + maxx; j < n; j++){
            if(s[j] <= s[i] * p){
                res = j - i + 1;// Elements between ji
                if(res > maxx)
                    maxx = res;
            }
                else
                    break;
                    
        }
    }

    printf("%d\n",maxx);
    return 0;
}
Copy the code

Topic link