你好,欢迎来到电脑编程技巧与维护杂志社! 杂志社简介广告服务读者反馈编程社区  
合订本订阅
 
 
您的位置:技术专栏 / C专栏
hdu 3530 Subsequence(单调队列)
 
题意:求区间最值差在[m,k]范围内的最长区间。
 
解法类似于hdu 4123 Bob’s Race(单调队列或者rmq)。稍微有一点点的不一样而已。
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<stdio.h>  
#include<string.h>  
#include<algorithm>  
using namespace std ;  
    
const int maxn = 111111 ;  
int n , m , num[maxn] , k ;  
struct Deque {  
    int val[2][maxn], pos[2][maxn];  
    int star[2] , tail[2] ;  
    void init () {  
        star[0] = 1 ;  
        tail[0] = 0 ;  
        star[1] = 1 ;  
        tail[1] = 0 ;  
    }  
    int judge (int c, int v) {  
        return c ^ (val[c][tail[c]] < v);  
    }  
    void push (int id, int v) {  
        int i ;  
    //  printf ( "id = %d , v = %d\n" , id , v ) ;  
        for ( i = 0 ; i < 2 ; i ++ ) {  
            while ( star[i] <= tail[i] && judge ( i , v ) )  
                tail[i] -- ;  
            val[i][++tail[i]] = v ;  
            pos[i][tail[i]] = id ;  
        }  
    }  
    void pop ( int c ) {  
        if ( star[c] <= tail[c] ) star[c] ++ ;  
    }  
    int gao ( int &last ) {  
        while ( (val[0][star[0]] - val[1][star[1]] > k ) ) {  
            if ( pos[1][star[1]] < pos[0][star[0]] ) {  
                last = pos[1][star[1]] ;  
                pop ( 1 ) ;  
            }  
            else {  
                last = pos[0][star[0]] ;  
                pop ( 0 ) ;  
            }  
        }  
        if ( val[0][star[0]] - val[1][star[1]] < m ) return -1 ;  
        return last ;  
    }  
} q ;  
    
int main () {  
    int i , j ;  
    while ( scanf ( "%d%d%d" , &n , &m , &k ) != EOF ) {  
        for ( i = 1 ; i <= n ; i ++ )  
            scanf ( "%d" , &num[i] ) ;  
        q.init () ;  
        int ans = 0 , last = 0 ;  
        for ( i = 1 ; i <= n ; i ++ ) {  
            q.push ( i , num[i] ) ;  
            int k = q.gao ( last ) ;  
            if ( k == -1 ) continue ;  
            last = k ;  
            ans = max ( ans , i - last ) ;  
        }  
        printf ( "%d\n" , ans ) ;  
    }  
    return 0 ;  
}

 

  推荐精品文章

·2024年9月目录 
·2024年8月目录 
·2024年7月目录 
·2024年6月目录 
·2024年5月目录 
·2024年4月目录 
·2024年3月目录 
·2024年2月目录 
·2024年1月目录
·2023年12月目录
·2023年11月目录
·2023年10月目录
·2023年9月目录 
·2023年8月目录 

  联系方式
TEL:010-82561037
Fax: 010-82561614
QQ: 100164630
Mail:gaojian@comprg.com.cn

  友情链接
 
Copyright 2001-2010, www.comprg.com.cn, All Rights Reserved
京ICP备14022230号-1,电话/传真:010-82561037 82561614 ,Mail:gaojian@comprg.com.cn
地址:北京市海淀区远大路20号宝蓝大厦E座704,邮编:100089