注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

GreenCloudS

 
 
 

日志

 
 

BZOJ-1293: [SCOI2009]生日礼物(离散化+单调队列)  

2014-02-28 19:33:00|  分类: oi,bzoj,数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

题目:http://www.lydsy.com/JudgeOnline/problem.php?id=1293


随便离散化一下,然后单调队列就可以了,单调队列中的位置单调,如果队首踢出去了仍然存在k种颜色,则踢开队首元素,队尾不需要维护。


代码:

  • #include <cstdio>

  • #include <algorithm>
  • #include <cstring>
  •  
  • using namespace std ;
  •  
  • #define inf 0x7fffffff
  • #define maxn 1000100
  • #define maxk 101
  •  
  • struct node {
  •     int v , t ; 
  •     void oper( int _v , int _t ) {
  •         v = _v , t = _t ;
  •     }
  •     bool operator < ( const node &a ) const {
  •         return t < a.t ;
  •     }
  • } a[ maxn ] , q[ maxn ] ;
  •  
  • int n , k , cnt[ maxk ] , counter = 0 , m = 0 , head = 1 , tail = 0 , ans = inf ;
  •  
  • int main(  ) {
  •     scanf( "%d%d" , &n , &k ) ;
  •     for ( int i = 0 ; i ++ < k ; ) {
  •         int x ; scanf( "%d" , &x ) ;
  •         while ( x -- ) {
  •             int pos ; scanf( "%d" , &pos ) ;
  •             a[ ++ m ].oper( i , pos ) ;
  •         }
  •     }
  •     sort( a + 1 , a + m + 1 ) ;
  •     memset( cnt , 0 , sizeof( cnt ) ) ;
  •     for ( int i = 1 , j ; i <= n ; ) {
  •         for ( j = i ; a[ j + 1 ].t == a[ j ].t && j < n ; ++ j ) ;
  •         for ( int h = i ; h <= j ; ++ h ) {
  •             q[ ++ tail ] = a[ h ] ;
  •             if ( ! ( cnt[ a[ h ].v ] ++ ) ) ++ counter ;
  •         }
  •         for ( ; cnt[ q[ head ].v ] > 1 ; -- cnt[ q[ head ++ ].v ] ) ;
  •         if ( counter == k ) ans = min( ans , a[ i ].t - q[ head ].t ) ;
  •         i = j + 1 ;
  •     }
  •     printf( "%d\n" , ans ) ;
  •     return 0 ;
  • }



  评论这张
 
阅读(2)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017