一场cf的题，题目链接；
题目大意是给你一串数字，你可以选择任意区间，让其中的每一个数的值是整个区间和的平均数，求最小的字典序。
这个题需要让前面的序列越小越好即寻找 r 令sum（1-r）/r最小，然后让1取代r继续类推，，暴力的写法T了；
一开始暴力的写了一发，T了
1 #include<bits/stdc++.h> 2 using namespace std; 3 double s[1000005] = {0.0}, sum[1000005] ={0.0}; 4 5 int main() 6 { 7 int n; 8 scanf("%d", &n); 9 for(int i = 1; i <= n; i++){ 10 scanf("%lf", &s[i]); 11 sum[i] = sum[i-1] + s[i]; 12 } 13 for(int i = 0; i < n; i++){ 14 double minn = 1000000000.0; 15 int k, pos; 16 for(k = i + 1; k <= n; k++){ 17 if((sum[k] - sum[i]) / (k - i) < minn){ 18 minn = 1.0 * (sum[k] - sum[i]) / (k - i); 19 pos = k; 20 if(minn == 1) break; 21 } 22 } 23 for(int k = i + 1; k <= pos; k++) s[k] = minn; 24 i = pos - 1; 25 } 26 for(int i = 1; i <= n; i++){ 27 printf("%.9lf\n", s[i]); 28 } 29 30 }
借鉴了大佬们的写法，太妙了
再引入s[i]的同时更新前端的序列；
#include<bits/stdc++.h> using namespace std; double s[1000005] = {0.0}, sum[1000005] ={0.0}, p[1000005] = {0}, q[1000005] = {0}; int top = 0; int main() { int n; scanf("%d", &n); for(int i = 1; i <= n; i++){ scanf("%lf", &s[i]); //sum[i] = sum[i-1] + s[i]; } for(int i = 1; i <= n; i++){ double sum = s[i]; int k = 1; while(top && sum*q[top] <= k*p[top]){ sum += p[top], k += q[top],top--; } p[++top] = sum, q[top] = k; // cout << p[top] << " " << q[top] << " " << top << endl; } for(int i = 1; i <= top; i++){ for(int j = 1; j <= q[i]; j++){ printf("%.9lf\n", 1.0 * p[i] / q[i]); } } }
原文：https://www.cnblogs.com/jrjxt/p/12292444.html