当前位置: 代码迷 >> 综合 >> Water Balance(CF618E/C)(单调栈)
  详细解决方案

Water Balance(CF618E/C)(单调栈)

热度:89   发布时间:2023-11-19 10:10:36.0

文章目录

  • 题目
  • 思路
  • 代码
  • 反省

题目

给你一个数列 a1,a2,...,ana_1,a_2,...,a_na1?,a2?,...,an?,每次选择一段区间 [l,r][l,r][l,r],将其中每个数变为他们的平均数,问最小字典序?
1≤n≤106,1≤ai≤1091\le n\le 10^6,1\le a_i\le10^91n106,1ai?109

思路

TM傻逼题
发现 、i、ii 前的操作不会改变 iii 前缀和 ,记前缀和为 pip_ipi? ,一次修改操作相当于将

pi=pl?1+pr?pl?1r?(l?1)?(i?l+1)p_i=p_{l-1}+\frac{p_r-p_{l-1}}{r-(l-1)}*(i-l+1)pi?=pl?1?+r?(l?1)pr??pl?1???(i?l+1)

(i,pi)(i,p_i)(i,pi?) 看成点后,这TM不就是两点连线吗
求字典序最小然后就是维护一个下凸壳,单调栈即可(不会的学学斜率优化)

代码

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<cstring>
#include<climits>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
//char buf[(1 << 21) + 1], *p1 = buf, *p2 = buf;
inline int read() {
    bool f=0;int x=0;char c=getchar();while(c<'0'||'9'<c){
    if(c==EOF)exit(0);if(c=='-')f=1;c=getchar();}while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();return !f?x:-x;
}
#define eps 1e-10
#define MAXN 1000000
#define INF 0x3f3f3f3f
double p[MAXN+5];
int Stk[MAXN+5],tp;
int main(){
    int n=read();for(int i=1;i<=n;i++)p[i]=p[i-1]+read();Stk[++tp]=0;for(int i=1;i<=n;i++){
    while(tp>=2&&(p[i]-p[Stk[tp]])/(i-Stk[tp])<(p[i]-p[Stk[tp-1]])/(i-Stk[tp-1]))tp--;Stk[++tp]=i;}for(int i=2;i<=tp;i++){
    double tmp=(p[Stk[i]]-p[Stk[i-1]])/(Stk[i]-Stk[i-1]);for(int j=Stk[i-1]+1;j<=Stk[i];j++)printf("%.10lf\n",tmp);}return 0;
}

反省

一定要多寻找题目特殊点,考试不要慌(老毛病又犯了)