有没有大佬帮忙剪个枝

朕爱学习 @ 2019-10-28 22:56:10

#include<bits/stdc++.h>
using namespace std;
int n,m,a[20000600],tot=999999999;

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(i==1)
        cout<<0<<endl;
        if(i<=m&&i!=1)
        {
            for(int j=1;j<=i-1;j++)
            {
                if(tot>a[j])
                tot=a[j];
            }
            cout<<tot<<endl;
        }
        if(i>m)
        {
            for(int j=i-m;j<=i-1;j++)
            {
                if(tot>a[j])
                tot=a[j];
            }
            cout<<tot<<endl;
        }
        tot=99999999999;
    }
    return 0;
}

by RAYMOND_7 @ 2019-11-15 08:54:00

没法优化，

只有树状数组、线段树和ST表能AC

给你个线段树代码

自己体会去吧

#include <cstdio>
inline int min(int i,int j){
    return i<j?i:j;
}
int n,m,a[2000004],tree[8000003],p;
inline void read(int &x){
    x=0;int k=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') k=-1;ch=getchar();}
    while(ch<='9'&&ch>='0') {x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
    return;
}
void build(int k,int l,int r){
    if(l==r) {
        tree[k]=a[l];return;
    }
    int mid=l+r>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    tree[k]=min(tree[k<<1],tree[k<<1|1]);
}
const int oo=2147483640;
int minn(int k,int l,int r,int x,int y){
    if(l>y||r<x)return oo;
    if(x<=l&&r<=y) return tree[k];
    int mid=l+r>>1,res;
    res=min(minn(k<<1,l,mid,x,y),minn(k<<1|1,mid+1,r,x,y));
    return res;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) read(a[i]);
    build(1,1,n);
    printf("0\n");
    for(int i=2;i<=n;i++){
        p=i-m>1?i-m:1;
        printf("%d\n",minn(1,1,n,p,i-1));
    }
    return 0;
}