题解 P3256 【[JLOI2013]赛车】

tylon2006 · 2019-07-06 18:09:47 · 题解

单调栈

时间复杂度为O(nlogn)，比半平面交常数小。

我才不会说是因为我懒得写半平面交

题解

如果一个人比你小，还比你强，你就肯定打不过他了

• 如果一辆车比你快(跟你一样快)，还比你出发点前，你就肯定追不上它了。

  即如果a.k>b.k&&a.v>=b.v，则a追不上b，拿不到第一。

  若有a为新加入的车，b为stk[top]，c为stk[top-1]，a追上b的时间小于b追上c的时间，则b不可能拿到第一，可以出栈(自行思考原因)。

• 如果一辆车跟你一样快，还跟你出发点一样，你就跟它并驾齐驱了(废话)。

  这使得a和b可能并列第一。

• 如果一辆车比你慢，比你出发点前，你就有可能追上它了。

  但这并不代表你就可以拿到第一，可能有比你速度快的在你前面或你后面的比你速度快的在你追上之前超你车。

• 如果一辆车比你快，比你出发点后，你就有可能被它追上了。

  这导致你可能在拿到第一之前被超车。

考虑这四种情况，就可以愉快地使用单调栈解题了。

把所有的车按v从小到大排序，v相同的按k从小到大排序。

然后每次加入一个车，再将栈中不可能拿第一的车出栈，最后该车入栈。

算完输出一下栈里车的编号就好啦qwq~

代码

#include<bits/stdc++.h>
using namespace std;
int stk[10010],top,n;
struct data{
    int k,v,id;
}a[10010];
bool cmp(data x,data y){
    if(x.v==y.v) return x.k<y.k;
    return x.v<y.v;
}
bool cmp1(int x,int y){
    return a[x].id<a[y].id;
}
double tim(data a,data b){//计算追及时间
    if(a.v==b.v) return 2e9;//防止除0 虽然似乎没有这样的数据
    return double(a.k-b.k)/(b.v-a.v);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) a[i].id=i;
    for(int i=1;i<=n;i++)
    scanf("%d",&a[i].k);
    for(int i=1;i<=n;i++)
    scanf("%d",&a[i].v);
    sort(a+1,a+n+1,cmp);
    stk[++top]=1;
    for(int i=2;i<=n;i++){
        while(top&&((a[i].k>a[stk[top]].k)||(top>1&&tim(a[stk[top]],a[i])<tim(a[stk[top-1]],a[stk[top]]))/*||(a[i].v==a[stk[top]].v&&a[i].k>a[stk[top]].k)*/)) top--;//注释部分然并卵
        stk[++top]=i;
    }
    printf("%d\n",top);
    sort(stk+1,stk+top+1,cmp1);
    for(int i=1;i<=top;i++)
    printf("%d ",a[stk[i]].id);
}