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

GreenCloudS

 
 
 

日志

 
 

3190: [JLOI2013]赛车(离散化+栈)  

2014-01-11 20:54:00|  分类: 栈,bzoj,oi |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


很弱的一道题:把所有赛车看成一条直线:y = vi * t + ki( t 表示时间 ),那么这道题便成了求存在t属于[0,正无穷)使得直线的y值在所有直线中最大(允许存在一样大的)的数目,那么把斜率升序排序,然后用个栈维护就可以了,注意点细节。(最开始没有排序WA了两次...QaQ...)


代码:

  • #include <cstdio>
  • #include <algorithm>
  • #include <cstring>
  •  
  • using namespace std ;
  •  
  • #define MAXN 10010
  •  
  • struct Line {
  •     int k , b , t ;
  •     bool operator < ( const Line &a ) const {
  •         return k < a.k || ( k == a.k && b > a.b ) ;
  •     }
  •     bool operator == ( const Line &a ) const {
  •         return k == a.k && b == a.b ;
  •     }
  • } line[ MAXN ] ;
  •  
  • int Stack[ MAXN ] , top = 0 , ans[ MAXN ] , ansn = 0 , n ;
  •  
  • struct Pos {
  •     double x , y ;
  •     Pos( double _x , double _y ) :x( _x ) ,y( _y ) {
  •     }
  • };
  •  
  • double Value( int a , double x ) {
  •     return line[ a ].k * x + line[ a ].b ;
  • }
  •  
  • Pos Cross( int a , int b ) {
  •     double x = double( line[ b ].b - line[ a ].b ) / double( line[ a ].k - line[ b ].k ) ;
  •     return Pos( x ,Value( a , x ) ) ;
  • }
  •  
  • int main(  ) {
  •     scanf( "%d" , &n ) ;
  •     for ( int i = 0 ; i ++ < n ; )scanf( "%d" , &line[ i ].b ) ;
  •     for ( int i = 0 ; i ++ < n ; )scanf( "%d" , &line[ i ].k ) ;
  •     for ( int i = 0 ; i ++ < n ; ) line[ i ].t = i ;
  •     sort( line + 1 , line + n + 1 ) ;
  •     for ( int i = 0 ; i ++ < n ; ) {
  •         if ( top && line[ Stack[ top ] ].k == line[ i ].k ) continue ;
  •         while ( top ) {
  •             Pos p =Cross( i , Stack[ top ] ) ;
  •             if ( p.x < 0 ) top -- ; else
  •             if ( top > 1 &&Value( Stack[ top - 1 ] , p.x ) > p.y ) top -- ;
  •             else break ;
  •         }
  •         Stack[ ++ top ] = i ;
  •     }
  •     for ( int i = 0 ; i ++ < top ; ) {
  •         for ( int j = Stack[ i ] ; j <= n && line[ j ] == line[ Stack[ i ] ] ; j ++ ) ans[ ++ ansn ] = line[ j ].t ;
  •     }
  •     sort( ans + 1 , ans + ansn + 1 ) ;
  •     printf( "%d\n" , ansn ) ;
  •     for ( int i = 0 ; i ++ < ansn - 1 ; )printf( "%d " , ans[ i ] ) ;
  •     printf( "%d\n" , ans[ ansn ] ) ;
  •     return 0 ;
  • }



  评论这张
 
阅读(7)| 评论(3)
推荐 转载

历史上的今天

评论

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

页脚

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