題目描述
有 n 道不同難度的題栓辜，你要從中選出合適的題目組成一套競賽試題测暗。試題各題之間難度逐級(jí)遞增钧萍，且除最后一題以外每道題的難度不低于后一道題的一半窄俏。求試題最多可以包含的題數(shù)狈邑。
輸入
輸入第一行含有一個(gè)整數(shù) n (1 ≤ n ≤ 2 * 10 ^ 5) 城须，表示題目的個(gè)數(shù)。
輸入第二行含有 n 個(gè)整數(shù) a[1], a[2], ... , a[n] (a[i] ≤ 10 ^ 9) 米苹，表示各個(gè)題目的難度糕伐。輸入保證不重復(fù)且從小到大排列。
輸出
輸出一個(gè)表示最大題數(shù)的整數(shù)蘸嘶。
樣例
Input
10
1 2 5 6 7 10 21 23 24 49
Output
4
題目分析
可以把每個(gè)輸入看作只具有“連續(xù)”（a[i] ≤ a[i-1] * 2 ）和“斷開”（a[i] > a[i-1] * 2）兩種狀態(tài)良瞧。容易得知若 a[m] 和 a[n] 連續(xù)則 a[m], a[m+1], ... , a[n] 皆連續(xù)，故問題化為求最大連續(xù)子序列训唱。
此類問題有通用的 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;
}
