題目鏈接
problem
給出一個長度為n的序列，每次可以選擇一個區間\([l,r]\)并將區間\([l,r]\)內的數字全部變為這些數字的平均數，該操作可以進行任意多次，
求出進行任意次操作后可以得到的字典序最小的序列，
solution
可以證明不存在一個數字被進行兩次或以上運算，即不存在如下情況：
顯然\([2,3]\)處的平均值小于\([1,2]\)處的平均值（否則紅色線不會包含2,3），4處的值大于\([1,3]\)的平均值（否則紅色線會包含4），然后藍色線進行選擇的時候，因為\([1,3]\)內的值全都變成了\([1,3]\)的平均值，而且\([1,3]\)的平均值又比4處的值小，所以藍色線肯定會包含1號位置，
所以就列舉一下每個區域的右端點，如果前面劃分的區域加上當前區域后平均值變小，那么就這這兩個區域合并即可，
code
/*
* @Author: wxyww
* @Date: 2020-02-10 09:22:11
* @Last Modified time: 2020-02-10 09:32:02
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 1000010;
ll read() {
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9') {
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
ll a[N],q[N],p[N],top;
int main() {
int n = read();
for(int i = 1;i <= n;++i) a[i] = read();
for(int i = 1;i <= n;++i) {
ll sum = a[i],cnt = 1;
while(top && q[top] * cnt >= sum * p[top]) {
sum += q[top];cnt += p[top];--top;
}
q[++top] = sum;p[top] = cnt;
}
for(int i = 1;i <= top;++i) {
double t = 1.0 * q[i] / p[i];
for(int j = 1;j <= p[i];++j) {
printf("%.9lf\n",t);
}
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/91949.html
標籤：其他
上一篇：什么是陣列？