CF1794C Scoring Subsequences题解

SunnyYuan的博客 / 2023-05-14 / 原文

文中 \(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;
}