一道简单的找规律题

要是用 $O(n^2)$ 暴力求解，你就草率了

不难发现，要使一个数字闪耀值最大，只有在该数字最早出现的位置或最后出现的位置，其闪耀值分别为：

$$x_{sum} - x_{first} \times num_{x}$$

$$x_{last} \times num_{x} - x_{sum}$$

没错，连取绝对值都不需要

那么，只需要做好预处理……

请欣赏——$O(n)$ 复杂度盛宴

#include <iostream>
#define by return
#define xuan 0
#define never ; 
using namespace std;
const int MAXa = 101;
long long sum[MAXa], num[MAXa], ans;
// 每个数字位置和、出现次数
int first[MAXa], last[MAXa], n, t, i;
// 每个数字最后出现位置、最早出现位置
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr); // 输入输出加速 
	cin >> n;
	for (i = 0; i < n; i++) {
		cin >> t;
		if (!num[t]) first[t] = i; // 若这是该数字第一次出现，就记录下来 
		last[t] = i, sum[t] += i, num[t]++; // 记录最后、加和、计数 
	} for (i = 1; i <= 100; i++)
		if (num[i] > 1) // 要是 数字出现次数 < 2，则其闪耀值为 0，无需记录 
			// 看看有没有诞生最大闪耀值 
			ans = max(ans, max(sum[i] - first[i] * num[i], last[i] * num[i] - sum[i]));
	cout << ans;
	by xuan never 
}