题目描述
有 n 道不同难度的题，你要从中选出合适的题目组成一套竞赛试题。试题各题之间难度逐级递增，且除最后一题以外每道题的难度不低于后一道题的一半。求试题最多可以包含的题数。
输入
输入第一行含有一个整数 n (1 ≤ n ≤ 2 * 10 ^ 5) ，表示题目的个数。
输入第二行含有 n 个整数 a[1], a[2], ... , a[n] (a[i] ≤ 10 ^ 9) ，表示各个题目的难度。输入保证不重复且从小到大排列。
输出
输出一个表示最大题数的整数。
样例
Input
10
1 2 5 6 7 10 21 23 24 49
Output
4
题目分析
可以把每个输入看作只具有“连续”（a[i] ≤ a[i-1] * 2 ）和“断开”（a[i] > a[i-1] * 2）两种状态。容易得知若 a[m] 和 a[n] 连续则 a[m], a[m+1], ... , a[n] 皆连续，故问题化为求最大连续子序列。
此类问题有通用的 O(n) 、online 算法，代码如下。
AC代码
#include<iostream>
#include<algorithm>
constexpr int maxin{1000000003};
int main() {
std::ios::sync_with_stdio(false);
int n; std::cin >> n;
int max{0};
int prev{maxin}, cnt{0}; for (int i{0}; i < n; ++i) {
int tmp; std::cin >> tmp;
if (tmp <= prev * 2) {prev = tmp; ++cnt;}
else {max = std::max(max, cnt); prev = tmp; cnt = 1;}
}
std::cout << std::max(max, cnt) << std::endl;
}
