https://ac.nowcoder.com/acm/contest/8282

C - brz的序列

 

题意：给定一个数列，每次操作选择一个数变成左右两个数的平均数，可以进行任意次操作，问数列总和最小是多少？

单调栈

当一个数列是等差数列时，操作不会改变任何数，否则一定可以继续变小。

所以就是要把原数列变成一些等差数列。

以 (i,ai)(i,a_i) 为点，在同一个等差数列中表示在同一条直线上。

画图能发现就是要找到一个下凸包。

这样把等差数列变成凸包，再用单调栈维护也算是套路了，要记住。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
int n;
double a[N];
typedef pair<double, double>pii;
pii st[N];
int tp;
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)scanf("%lf", &a[i]);
	st[tp++] = { 1,a[1] };
	for (int i = 2; i <= n; i++) {
		while (tp > 1 && (a[i] - st[tp - 1].second) / (i - st[tp - 1].first) <= (a[i] - st[tp - 2].second) / (i - st[tp - 2].first)) {
			tp--;
		}
		st[tp++] = { i,a[i] };
	}
	double ans = 0;
	for (int i = 0; i < tp - 1; i++) {
		ans += (st[i].second + st[i + 1].second)*(st[i + 1].first - st[i].first + 1) / 2;
	}
	for (int i = 1; i < tp - 1; i++)ans -= st[i].second;
	printf("%.10lf\n", ans);
	return 0;
}