正題

題目鏈接:https://codeforces.com/contest/536/problem/C

---

題目大意

$n$個人，第$i$個人的游泳速度$s_i$，跑步速度是$r_i$。如果跑道長度是$R$，泳道長度是$S$那么一個人的用時就是$\frac{R}{r_i}+\frac{S}{s_i}$，在$R/S$不定的情況下然后求出所有可能是用時最短的人。

$1\le n\le 10^5,1\le s_i,r_i\le 10^4$

---

解題思路

設(shè)$k=\frac{R}{S}$，那么用時可以化為$\frac{k}{r_i}+\frac{1}{s_i}$。

然后對于一個點$(?\frac{1}{r_i},\frac{1}{s_i})$，我們可以視為用一條斜率為$k$的斜線去截這些點然后讓截距最小。

直接維護一個凸殼就好了，然后注意因為$R/S$都是正數(shù)所以$k$也得是正數(shù)，所以要把后段丟掉。

時間復雜度：$O(n\log n)$

當然還有一個更神奇的做法，因為對于一個$s_i$我們只需要最大的$r_i$所以有用的點數(shù)不超過$10^4$，可以直接平方暴算。

---

code

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=2e5+10; const double eps=1e-8; struct node{double x,y;int id; }q[N]; int n,top,s[N],ans[N],l[N]; bool cmp(node x,node y) {return (x.x==y.x)?(x.y>y.y):(x.x<y.x);} double slope(node a,node b) {return (b.y-a.y)/(b.x-a.x);} int main() {scanf("%d",&n);for(int i=1;i<=n;i++){double x,y;q[i].id=i;scanf("%lf%lf",&x,&y);q[i].x=1e5/x;q[i].y=1e5/y;}sort(q+1,q+1+n,cmp);for(int i=1;i<=n;i++)if(q[i].x==q[i-1].x&&q[i].y==q[i-1].y)l[i]=l[i-1];else l[i]=i;for(int i=1;i<=n;i++){if(q[i].x==q[i+1].x)continue;while(top>1&&slope(q[s[top-1]],q[s[top]])-eps>slope(q[s[top-1]],q[i]))top--;s[++top]=i;}for(int i=1;i<=top;i++){for(int j=l[s[i]];j<=s[i];j++)ans[q[j].id]=1;if(q[s[i]].y<=q[s[i+1]].y)break;}for(int i=1;i<=n;i++)if(ans[i])printf("%d ",i);return 0; }

總結(jié)

以上是生活随笔為你收集整理的CF536C-Tavas and Pashmaks【凸壳】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。