JDOJ-2042: [JLOI2013]赛车 单调栈+图像分析

Description

这里有一辆赛车比赛正在进行,赛场上一共有N辆车,分别称为个g1,g2……gn。赛道是一条无限长的直线。最初,gi位于距离起跑线前进ki的位置。比赛开始后,车辆gi将会以vi单位每秒的恒定速度行驶。在这个比赛过程中,如果一辆赛车曾经处于领跑位置的话(即没有其他的赛车跑在他的前面),这辆赛车最后就可以得奖,而且比赛过程中不用担心相撞的问题。现在给出所有赛车的起始位置和速度,你的任务就是算出那些赛车将会得奖

对于100%的数据N<=10000, 0<=ki<=109, 0<=vi<=109

单调栈--CKH小朋友曾经讲过。https://ahackh.ac.cn/

想到可以对于每一个车画出一个v-t图像,然后想到一个车处于过领先位置说明这条直线在上方没有被覆盖。所以我们可以。。这样想

先按速度排序。然后向栈里扔,当前一条的出发点比我前,直接弹掉。当前一个出发点的前面已经被一个车挡住时,看能不能将后米娜那部分也挡住,如果可以就弹掉。直到不能弹为止。计算被上一个挡住的部分。

我们想这个算法的正确性。

1.不会有情况将速度小的车挡掉,而中的没有挡掉,画个图将速度大的直线平移一下就可以看出来。所以说,只能从栈顶向下弹。

2.为什么挡住的部分用上一个元素计算而不是更前面的。

假设有那么一个更前面的已经挡住他的更长的部分,那么上一个元素一定已经被搞掉了。删一个元素与当前元素交点一定大于前一个元素与跟更前面的交点,显然,前一个元素只要村后下来,对当前元素的消耗是最大的。

3.小心PE

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n,top,z[11000];
struct node
{
    int dis,v,id;
    double cross;
}a[11000];
bool cmp(node x,node y)
{
    return x.v==y.v ? x.dis<y.dis:x.v<y.v;
}
double find_cross(int x,int y)
{
    return 1.0*(a[y].dis-a[x].dis)/(a[x].v-a[y].v);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        a[i].id=i,scanf("%d",&a[i].dis);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i].v);
    sort(a+1,a+n+1,cmp);
    z[1]=1;top=1;
    int tmp;
    for(int i=2;i<=n;i++)
    {
        while(top)
        {
            tmp=z[top];
            if(a[i].dis>a[tmp].dis) top--;
            else if(1.0*a[i].dis+1.0*a[i].v*a[tmp].cross>1.0*a[tmp].dis+1.0*a[tmp].v*a[tmp].cross) top--;
            else break;
        }
        if(top!=0) a[i].cross=find_cross(z[top],i);
        z[++top]=i;
    }
    printf("%d\n",top);
    if(top==0) return 0;
    for(int i=1;i<=top;i++)
        z[i]=a[z[i]].id;
    sort(z+1,z+top+1);
    printf("%d",z[1]);
    for(int i=2;i<=top;i++)
        printf(" %d",z[i]);
    return 0;
}

 

发表评论

邮箱地址不会被公开。 必填项已用*标注