This article is participating in the nuggets team number online activity, click to see the dachang spring recruiting positions

I. Title Description:

Codeforces 1029B creates games Codeforces 1029B creates games

You are given an ascending array a1… ,ana_1,… ,a_na1,… An asks you to find a subsequence b1… ,bmb_1,… ,b_mb1,… , BM meets ∀ I ∈[I, M −1]\forall I \in [I, M-1]∀ I ∈[I, M −1] all have BI +1≤ 2BIB_ {I +1} \leq 2b_IBi +1≤ 2BI, and makes the size of this subset maximum.

Ii. Analysis of Ideas:

At first glance, this problem seems difficult. Finding subsets that satisfy this condition in a set is a combinatorial problem, and the number of possible combinations is 2n2^n2n. Obviously, it can’t be written using naive combinations of enumerations.

If a problem looks complicated and still has a solution, then it must have a way to simplify, this problem only gives the relationship limit of adjacent elements, we can use this as a breakthrough point to find the law.

  1. Let’s say that aia_iai is the smallest of the elements to be selected, so the elements before aia_iai do not satisfy this condition, so we only need to consider the elements after aia_iai, and since the array is ordered, we only need to consider the condition ≤2ai\leq 2a_i≤2ai.

  2. Assuming that two elements satisfy this condition, we must add the smaller one first, and then the larger one, because ≤2ai\leq 2a_i≤2ai gets loosier and loosier as we add more and more elements, and then we will find the largest subsequence that satisfies this condition starting with aia_iai. Here we can also see that it is more appropriate to describe the result set as a substring, because if ai+1a_{I +1}ai+1 does not satisfy the condition, then the following is even more impossible, so there is no possibility of selecting “disconnect”.

  3. Once we realize that only subsets of the selection can be substrings, the answer is clear, because the selection cannot be “broken”, so the substrings must not be adjacent, so we simply find all the substrings that satisfy this condition from beginning to end, and output the smallest substring length.

  4. Since we iterate sequentially, and each new element is only relevant to the previous digit, we can use a variable pre to record the previous digit instead of storing the input array, and then iterate over the answer. Note that selecting only one element always satisfies the condition, so we’ll initialize ans to 1.

Iii. AC Code:

#include <iostream>
using namespace std;

int main(a) {
    int n;
    cin >> n;

    int pre = 0;
    int ans = 1, cnt = 1;
    for (int i = 0; i < n; ++i) {
        int num;
        cin >> num;
        if (num <= pre * 2) {
            ++cnt;
            ans = max(ans, cnt);
        } else {
            cnt = 1;
        }
        pre = num;
    }

    cout << ans << endl;
}
Copy the code

Iv. Summary:

Construct subarrays that satisfy certain conditions. For example, change the above condition to the condition that the adjacent elements are less than a certain value. The method is the same. So encountered this kind of routine topic we should be timely induction, do a problem can do a class of problems, to achieve twice the result with half the effort.