题目点这里 一个非常好玩的题目 一开始各种推结论没有推出来，后来看到一位大佬提到“凸包”突然明白 首先去掉所有两项速度都比某个人慢的那些，让后开始分析剩下的人 我们设函数 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.b−1./a.b)/(1./a.a−1./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[r−1]])) −−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 ] ) ; } }
