51Nod1543 铁人两项

xiaoxiao2021-03-01  45

题目点这里 一个非常好玩的题目 一开始各种推结论没有推出来,后来看到一位大佬提到“凸包”突然明白 首先去掉所有两项速度都比某个人慢的那些,让后开始分析剩下的人 我们设函数 Ti(x)=x/ri+1/si T i ( x ) = x / r i + 1 / s i R/S=x R / S = x 我们就可以通过比较 Ti(x) T i ( x ) 得到各个选手的用时大小关系 又因为显然 Ti(x) T i ( x ) 是一条直线,所以可以直接单调栈维护上凸壳 最后留在凸包里面的直线就是可以胜利的选手 (p.s不太会写凸包,胡乱写的,数据很水所以过了,如果有人发现有错误请务必在评论区留言) #include<stdio.h> # i n c l u d e < s t d i o . h > #include<string.h> # i n c l u d e < s t r i n g . h > #include<algorithm> # i n c l u d e < a l g o r i t h m > using namespace std; u s i n g   n a m e s p a c e   s t d ; struct p{ int a,b,i; } s[200010]; s t r u c t   p {   i n t   a , b , i ;   }   s [ 200010 ] ; int n,m,q[200010],l,r,A[200010],t; i n t   n , m , q [ 200010 ] , l , r , A [ 200010 ] , t ; inline double cross(p a,p b){ i n l i n e   d o u b l e   c r o s s ( p   a , p   b ) { return (1./b.b1./a.b)/(1./a.a1./b.a); r e t u r n   ( 1. / b . b − 1. / a . b ) / ( 1. / a . a − 1. / b . a ) ; } } inline bool c1(p a,p b){ i n l i n e   b o o l   c 1 ( p   a , p   b ) { return a.a==b.a?a.b>b.b:a.a<b.a; r e t u r n   a . a == b . a ? a . b > b . b : a . a < b . a ; } } inline bool c2(p a,p b){ i n l i n e   b o o l   c 2 ( p   a , p   b ) { return a.a==b.a?a.b>b.b:a.a>b.a; r e t u r n   a . a == b . a ? a . b > b . b : a . a > b . a ; } } int main(){ i n t   m a i n ( ) { scanf("%d",&n); s c a n f ( " % d " , & n ) ; for(int i=1;i<=n;++i) scanf("%d%d",&s[i].a,&s[i].b),s[i].i=i; f o r ( i n t   i = 1 ; i <= n ; + + i )   s c a n f ( " % d % d " , & s [ i ] . a , & s [ i ] . b ) , s [ i ] . i = i ; sort(s+1,s+1+n,c2); s o r t ( s + 1 , s + 1 + n , c 2 ) ; for(int i=1,mx=0;i<=n;++i){ f o r ( i n t   i = 1 , m x = 0 ; i <= n ; + + i ) { if(s[i].b>mx  s[i].b==mx && s[i].a==s[m].a) s[++m]=s[i]; i f ( s [ i ] . b > m x   ‖ ‖   s [ i ] . b == m x   & &   s [ i ] . a == s [ m ] . a )   s [ + + m ] = s [ i ] ; mx=max(mx,s[i].b); m x = m a x ( m x , s [ i ] . b ) ; } } sort(s+1,s+1+m,c1); q[l=r=1]=1; s o r t ( s + 1 , s + 1 + m , c 1 ) ;   q [ l = r = 1 ] = 1 ; for(int i=2;i<=m;++i){ f o r ( i n t   i = 2 ; i <= m ; + + i ) { while(l<=r && cross(s[i],s[q[r]])<cross(s[q[r]],s[q[r1]])) r; w h i l e ( l <= r   & &   c r o s s ( s [ i ] , s [ q [ r ] ] ) < c r o s s ( s [ q [ r ] ] , s [ q [ r − 1 ] ] ) )   − − r ; q[++r]=i; q [ + + r ] = i ; } } for(;l<=r;++l) A[++t]=s[q[l]].i; sort(A+1,A+1+t); f o r ( ; l <= r ; + + l )   A [ + + t ] = s [ q [ l ] ] . i ;   s o r t ( A + 1 , A + 1 + t ) ; for(int i=1;i<=t;++i) printf("%d ",A[i]); f o r ( i n t   i = 1 ; i <= t ; + + i )   p r i n t f ( " % d   " , A [ i ] ) ; } }

转载请注明原文地址: https://www.6miu.com/read-4199921.html

最新回复(0)