关于上溢
  • 板块P2251 质量检测
  • 楼主Kun_9
  • 当前回复4
  • 已保存回复4
  • 发布时间2022/7/2 08:52
  • 上次更新2023/10/27 22:06:54
查看原帖
关于上溢
358795
Kun_9楼主2022/7/2 08:52

数组f[MAXN][32]在赋初值的时候上溢但是也AC了,求解

#include <bits/stdc++.h>

#define MAXN 101010
#define ll long long
#define mod 10000

using namespace std;

int n, m;
int f[MAXN][32], lg[MAXN];
int a[MAXN];

void mylog( ){
    for( int i = 1; i <= MAXN; i++ )
        lg[i] = lg[i / 2] + 1;
    return;
}

void ST( ){
    for( int j = 1; j <= lg[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] );
    return;
}

int check( int l, int r ){
    int k = lg[ r - l + 1 ] - 1;
    return min( f[l][k], f[r - ( 1 << k ) + 1][k] );
}

int main( ){

    mylog( );

    scanf("%d%d",&n,&m);
    
    for( int i = 1; i <= n; i++ )
        for( int j = 1; j <= 32; j++ )
            f[i][j] = MAXN;

    for( int i = 1; i <= n; i++ )
        scanf("%d",&a[i]), f[i][0] = a[i];
    
    ST( );

    for( int i = 1; i <= n - m + 1; i++ )
        printf("%d\n",check( i, i + m - 1 ));

	return 0;
}
2022/7/2 08:52
加载中...