首页 > 编程语言 > 详细

区间伸缩算法小礼包

时间:2019-10-15 00:04:38      阅读:181      评论:0      收藏:0      [点我收藏+]

区间伸缩算法小礼包

主要还是用来优化结合其他算法时的复杂度,ssw02就用两道题浅谈一下总结吧

欢迎转载ssw02的博客:https://www.cnblogs.com/ssw02/p/11674544.html


逛画展

题面
博览馆有一个很奇怪的规定,就是在购买门票时必须说明两个数字,

a和b,代表他要看展览中的第 a 幅至第 b 幅画(包含 a 和 b)之间的所有图画,而门票

的价钱就是一张图画一元。

为了看到更多名师的画,wangjy希望入场后可以看到所有名师的图画(至少各一张)。

可是他又想节省金钱。。。

作为wangjy的朋友,他请你写一个程序决定他购买门票时的 a 值和 b 值。

思路

这道题比较水,我们考虑存在任何一个恰好的合法区间 [L,R] 时,当 L 向右移动时,R 不可能向左移动,所以 L,R 在最小合法时的移动方向一定一样。

然后直接上代码了

代码

#include<bits/stdc++.h>
using namespace std ;
const int MAXN = 1000005 ;
inline int read(){
    int s=0 ; char g=getchar() ;while( g>'9'||g<'0' )g=getchar() ;
    while( g>='0'&&g<='9' )s=s*10+g-'0',g=getchar() ; return s;
}
int  N , M , cnt[ 2005 ] , a[ MAXN ] ;
int  q[ MAXN ] , l , r , tot , ansl , ansr , ans ;
int main(){
    N = read() , M = read() , ans = (1<<30) ;
    for( int i = 1 ; i <= N ; ++i )a[i] = read() ;
    for( l = 1 , r = 0 ; l <= N ; ){
        while( tot < M && r < N ){
            if( cnt[ a[++r] ] == 0 )tot++ ;
            cnt[ a[r] ]++ ;
        }
        while( l <= N ){
            if( cnt[ a[l] ] == 1 )break ;
            else
                cnt[ a[l++] ]-- ;
        }
        if( tot != M )break ;
        if( r-l+1 < ans )//记录较小的 
            ans = r-l+1 , ansl = l , ansr = r ;
        if( cnt[ a[l] ]==1 )tot--;
        cnt[a[l]]--,l++ ;
    }
    cout<<ansl<<" "<<ansr ;
    return 0 ;
}

[SCOI2009]生日礼物

先放上面那道题是为了减轻这道题的思维难度(不过本来这道题也没什么思维难度)

区别:1.范围特别大,当有效的点最多还是 1e6 个 , 考虑读入后离散化 ,对于每个点上存储的颜色使用vector存一下即可。

然后就是把上面的单个修改改为离散化后的单点多个修改即可。还是使用类似单调队列的区间推移操作即可。

#include<bits/stdc++.h>
using namespace std ;
inline int read(){
    int s=0 ; char g=getchar() ; while( g>'9'||g<'0' )g=getchar() ;
    while( g>='0'&&g<='9' )s=s*10+g-'0',g=getchar() ; return s ;
}
int N , K , tot , cnt[ 61 ] , p[ 1000005 ] , id[ 1000005 ] ;
vector<int>num[ 1000005 ] ;
struct ap{
    int  loc , col ,  id ;
}t[ 1000005 ] ; 
inline bool cmp( ap x , ap y ){
    return (x.loc==y.loc)?(x.col<y.col):(x.loc < y.loc) ;
}
int main(){
    N = read() , K = read() ; int m1 , m2=0 ;
    for( int i = 1 ; i <= K ; ++i ){
        m1 = read() ;
        for( int j = 1 ; j <= m1 ; ++j )t[++m2].loc=read(),t[m2].col=i ;
    } 
    sort( t+1 , t+N+1 , cmp ) ;
    int now = 0 , loc = 0 , ans = 2147483647 ;
    for( int i = 1 ; i <= N ; ++i ){
        if( now != t[i].loc )now=t[i].loc,loc++,id[loc] = now ; 
        num[loc].push_back(t[i].col) ; 
    } 
    for( int l = 1 , r = 0 ; l <= loc ; ){
        while( tot < K && r < loc ){
            int number = num[ ++r ].size() ;
            for( int j = 0 ; j < number ; ++j ){
                if( cnt[ num[r][j] ] == 0 )tot++ ;
                cnt[ num[r][j] ]++ ;
            } 
        }
        while( l <= loc ){
            bool flag = true ; int number = num[l].size() ;
            for( int j = 0 ; j < number ; ++j )
                if( cnt[ num[l][j] ] == 1 ){flag=false;break;}
            if( flag ){
                for( int j = 0 ; j < number ; ++j )
                    cnt[ num[l][j] ]-- ;
                ++l ;
            }
            else break ;
        }
        if( tot != K )break ;
        if( id[r]-id[l] < ans )
            ans = id[r]-id[l] ;
        int number = num[l].size() ;
        for( int j = 0 ; j < number ; ++j ){
            if( cnt[ num[l][j] ] == 1 )tot-- ;
            cnt[ num[l][j] ]-- ; 
        }
        l++ ;
    }
    cout<<ans ;
    return 0 ;
}

欢迎转载ssw02的博客:https://www.cnblogs.com/ssw02/p/11674544.html

区间伸缩算法小礼包

原文:https://www.cnblogs.com/ssw02/p/11674544.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!