蒟蒻60分求助,在线等,挺急的
查看原帖
蒟蒻60分求助,在线等,挺急的
1059536
yylz1031楼主2024/8/28 08:50
#include <bits/stdc++.h>

using namespace std ;

int n , m ;
int a [ 100005 ] ;
int dp [ 100005 ] [ 55 ] ;

int main() {
	
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m ;
	
	for ( int i = 1 ; i <= n ; i ++ )
		cin >> a [ i ] ;
	
	for ( int i = 1 ; i <= n ; i ++ )
		dp [ i ] [ 0 ] = a [ i ] ;
	
	for ( int j = 1 ; j <= 30 ; j ++ ) 
		for ( int i = 1 ; i <= n && i + ( 1 << ( j ) ) - 1 <= n ; i ++ ) 
			dp [ i ] [ j ] = min ( dp [ i ] [ j - 1 ] , dp [ i + ( 1 << ( j - 1 ) ) ] [ j - 1 ] ) ;
	
	for ( int i = 1 , j = m ; i <= n - m + 1 && j <= n ; i ++ , j ++ ) {
		int len = j - i + 1 ;
		int k = log2 ( len ) ;
		int ans = min ( dp [ i ] [ k - 1 ] , dp [ j - ( 1 << ( k - 1 ) ) + 1 ] [ k - 1 ] ) ;
		cout << ans << '\n' ;
	}
	
} 
2024/8/28 08:50
加载中...