[Acwing] 58周赛 4489. 最长子序列

前言

t a g : tag : tag: 思维 传送门 :

题意 : 给定一个 上升 的数组,求一个子序列使得子序列中的元素满足 a j ∗ 2 ≥ a j + 1 a_j*2\ge a_{j+1} aj​∗2≥aj+1​,询问合法子序列的最大长度

思路 : 因为给出的数组是 上升的

因此如果 a 1 ∗ 2 ≥ a 3 a_1*2\ge a_3 a1​∗2≥a3​存在,那么必然存在 a 1 ∗ 2 ≥ a 2 a_1 *2\ge a_2 a1​∗2≥a2​

则这个条件使得所求答案 连续, 因此我们只需要 O n On On的扫一遍即可

code :

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define IOS  ios::sync_with_stdio(false);
#define CIT  cin.tie(0);
#define COT  cout.tie(0);

#define ll long long
#define x first
#define y second
#define pb push_back
#define endl '\n'
#define all(x) (x).begin(),x.end()
#define Fup(i,a,b) for(int i=a;i=b;i--)
#define cer(a) cerr