这么玄学的时间复杂度都能过?(356ms)(o2 233ms)

P1440 求m区间内的最小值

log_and_long @ 2023-05-26 11:15:54

是不是数据太水了?

#include<bits/stdc++.h>
using namespace std;
int a,b,e,ans=0x7fffffff;
int c[10000001];
int jy;
inline int read() {
    int s = 0,w = 1;
    char ch = getchar();
    while (ch > '9' || ch < '0') {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch <= '9' && ch >= '0') s = (s << 1) + (s << 3) + (ch ^ 48),ch = getchar();
    return s * w;
}
inline void write(int n)
{
    if(n<0)
    {
        putchar('-');
        n=-n;
    }
    if(n>9)write(n/10);
    putchar(n%10+'0');
}
int work(int x){
    x--;
    int y=b,minn=0x7fffffff;
    if(x-y<jy){
        if(c[x]<=c[jy]){
            jy=x;
        }
        return c[jy];
    }
    if(c[x]<=c[jy]){
        jy=x;
        return c[x];
    }
    while(y--){
        if(minn>=c[x]){
            minn=c[x];
            jy=x;
        }
        x--;
    }
    return c[jy];
}
int main(){
    a=read();
    b=read();
    for(int i=1;i<=a;i++){
        e=b;
        c[i]=read();
    }
    write(0);
    printf("\n");
    for(int i=1;i<=b;i++){
        if(ans>=c[i]){
            ans=c[i];
            jy=i;
        }
        write(ans);
        printf("\n");
    }
    for(int i=b+2;i<=a;i++){
        write(work(i));
        printf("\n");
    }
    return 0;
}

by too_simple @ 2023-05-26 11:27:47

@log_and_long 您的work函数太高深了,看不懂


by log_and_long @ 2023-05-26 11:31:51

@too_simple 简单来说就是一步步找,在前一个区间找到的最小值和现在找到的值对比,如果超过范围就重新找最小值(我感觉这个数据很水,这都能过)


by log_and_long @ 2023-05-26 11:34:20

@too_simple 靠的是数据好坏的运气过的


|