Codeforces Round #618 E

题意：

给你一个n的数组，你可以进行无数次，选择区间使得区间内的值相加，然后区间的所有的值变成平均值。

使得最后数组的字典序最小

思路：

最后的数组一定是单调递增的，只要它比之前的平均值数大，就不会操作，如果比他小，需要进行操作到符合它的范围

用单调递减栈进行操作

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define il inline
#define it register int
#define inf 0x3f3f3f3f
#define lowbit(x) (x)&(-x)
#define mem(a,b) memset(a,b,sizeof(a))
#define mod 1000000007
const int maxn=1e6+10;
int n,m,t;
double a[maxn],ans[maxn];
int l[maxn],len[maxn];
int main(){
    scanf("%d",&n);
    for(it i=1;i<=n;i++){
        scanf("%lf",&a[i]);len[i]=1;
    }
    it top=1;l[1]=1;
    for(it i=2;i<=n;i++){
        double now=a[i],sum=a[i];
        while(top>=1 && a[l[top]]>now){
            len[i]+=len[l[top]];
            sum+=a[l[top]]*len[l[top]];
            now=sum/len[i];
            top--;
        }
        a[i]=sum/len[i];
        l[++top]=i;
    }
    it l1=0;
    while(top>=1){
        for(it i=1;i<=len[l[top]];i++){
            ans[++l1]=a[l[top]];
        }top--;
    }
    for(it i=l1;i;i--){
        printf("%.10lf
",ans[i]);
    }
    return 0;
}

补一道，单调栈

题意：

求数组n，连续的k，从头到n-k，其中每一段中最大的数字是什么

样例

5 3

1 5 3 4 2

输出

思路

从前到后，存进去比sta.top大的值，和已经存进去并且在区间内的值

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define il inline
#define it register int
#define inf 0x3f3f3f3f
#define lowbit(x) (x)&(-x)
#define mem(a,b) memset(a,b,sizeof(a))
#define mod 998244353
const int maxn=2e6+10;
int n,k;
int a[maxn],sta[maxn],ans[maxn],pos[maxn];
int main() {
    scanf("%d%d",&n,&k);
    for(it i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    int top=1,t=0;sta[top]=a[0];pos[top]=0;
    for(it i=1;i<k-1;i++){
        while(top>=1 && (a[i]>sta[top] || i-k>=pos[top])){
            top--;
        }
        sta[++top]=a[i];pos[top]=i;
    }
    for(it i=k-1;i<n;i++){
        while(top>=1 && (a[i]>sta[top] || i-k>=pos[top])){
            top--;
        }
        sta[++top]=a[i];pos[top]=i;
        it c=1;while(i-k>=pos[c]){c++;}
        printf("%d
",sta[c]);
    }
    return 0;
}

相关推荐