80 m了两个点

P1440 求m区间内的最小值

XXCCVV @ 2023-03-03 13:34:36

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<vector>
#include<cmath>
#include<stack>
#include<queue>
#include<map>
#include<set>
using namespace std;

int n,m;
int f[2000005][20],logn[2000005];

int main() {
    cin>>n>>m;
    int a;
    for(int i=1; i<=n; i++) {
        cin>>a;
        f[i][0]=a;
    }
    int now=0;
    for (int i=1; i<=n; i++) {
        if ((1 << (now+1))<=i) ++now;
        logn[i]=now;
    }
    for(int j=1; (1<<j)<=n; j++) {
        for(int i=1; i+(1<<j)-1<=n; i++) {
            f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        }
    }
    int x=-1,y,lognn,ans;
    while(n--) {
        x++;
        y=x-m+1;
        if(y<=0) {
            y=1;
        }
        lognn=logn[x-y+1];
        ans=min(f[y][lognn],f[x-(1<<lognn)+1][lognn]);
        cout<<ans<<endl;
//      cout<<x<<" "<<y<<endl;
    }
    return 0;
}

求助


by XXCCVV @ 2023-03-03 13:35:47

记录


by songzhihan2010 @ 2023-05-07 11:26:15

我也是qwq


|