简要题意
你有一个序列${a}$,你的每次操作可以把一段区间里的数全部变成这个区间的平均数，求能得到的字典序最小的序列
分析
我们发现字典序最小时显然${a_i}$单调不降
那么我们可以维护一个单调栈，栈里维护的值${l,r,avr}$，表示该段区间的左端点、右端点、平均值
每次插入${i,i,a_i}$,然后暴力循环取出栈顶的两个节点$x, y$（$y$在$x$后插入）,如果满足$y.avr<x.avr$则合并$x,y$，直到不能合并为止（具体细节可以看代码）
最后把栈中记录的值输出即可
代码
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
32
33
34
35
36
37
38
39
40
41
42
| #include <bits/stdc++.h>
#define R register
#define ll long long
#define sum(a, b, mod) (((a) + (b)) % mod)
const int MaxN = 1e6 + 10;
struct node
{
int l, r;
double sum, len;
};
int n;
double a[MaxN];
std::vector<node> vec;
int main()
{
int tmp;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &tmp), a[i] = tmp;
for (int i = 1; i <= n; i++)
{
vec.push_back((node){i, i, a[i], 1});
while (vec.size() >= 2 && (vec[vec.size() - 2].sum / vec[vec.size() - 2].len) >= (vec[vec.size() - 1].sum / vec[vec.size() - 1].len))
{
node x = (node){vec[vec.size() - 2].l, vec[vec.size() - 1].r, vec[vec.size() - 2].sum + vec[vec.size() - 1].sum, vec[vec.size() - 1].r - vec[vec.size() - 2].l + 1.0};
vec.pop_back(), vec.pop_back(), vec.push_back(x);
}
}
for (int i = 0; i < vec.size(); i++)
{
for (int j = vec[i].l; j <= vec[i].r; j++)
a[j] = (vec[i].sum / vec[i].len);
}
for (int i = 1; i <= n; i++)
printf("%.10lf\n", a[i]);
return 0;
}
|