文中 \(a\) 为题目中给的 \(a\)。
如果我们要求 \(a_1, a_2, a_3, \dots, a_m\) 的结果,
那么我们可以把 \(a\) 数组从后往前依次除以 \(i\),\(i\) 从 \(1\) 到 \(n\),
即为 \(\frac{a_1}{m},\frac{a_2}{m - 1},\frac{a_3}{m - 2},\dots,\frac{a_{m - 1}}{2},\frac{a_m}{1}\),并将其保存在数组 \(s\) 中。
因为 \(a_1 \leq a_2 \leq a_3 \leq \dots \leq a_m\),且 \(\frac{1}{i}\) 单调递增,所以 \(s_1 \leq s_2 \leq s_3 \dots \leq s_m\)。
那么我们自然而然地可以想到,每一次的结果就是末尾的几个数字的乘积(因为 \(s\) 越大越好),即 \(s_k \times s_{k + 1} \times \dots \times s_m\)。
那么 \(k\) 取多少呢?
我们只取对自己有利的部分,所以当 \(s_k \geq 1\) 且 \(s_{k - 1} < 1\) 时,我们可以达到最大值 \(ans = s_k \times s_{k + 1} \times \dots \times s_m\)。
因为 \(s\) 单调不下降,所以可以使用二分来得出要保留的数字 \(m - k\)。
对每一个 \(m\) 进行操作,\(1 \leq m \leq n\)。
时间复杂度:\(O(n \log n)\)。
C++代码
/*******************************
| Author: SunnyYuan
| Problem: C. Scoring Subsequences
| Contest: Codeforces Round 856 (Div. 2)
| URL: https://codeforc.es/contest/1794/problem/C
| When: 2023-03-06 08:30:32
|
| Memory: 256 MB
| Time: 2500 ms
*******************************/
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 100010;
int n, a[N];
void solve() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) {
int l = -1, r = i + 1;
while (l + 1 < r) {
int mid = (l + r) / 2;
if (a[i - mid + 1] >= mid) l = mid;
else r = mid;
}
cout << l << ' ';
}
cout << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) solve();
return 0;
}
标签:dots,Scoring,frac,CF1794C,题解,times,leq,int,include
From: https://www.cnblogs.com/PlayWithCPP/p/17399253.html