如果你用单调栈维护但是 WA on #10
查看原帖
如果你用单调栈维护但是 WA on #10
1083611
LLLLLL7381楼主2024/10/18 10:54

如果你的做法像这样:

struct node
{
    int a,b;
    int id;
    bool operator < (const node &x) const
    {
        if(a==x.a)
        {
            return b>x.b;
        }
        return a>x.a;
    }
}f[maxn];
int st[maxn],ans[maxn],top;
inline double get_crossx(node x,node y)
{
    return (double)(y.b-x.b)/(double)(x.a-y.a);
}
//后面用的单调栈,不解释

如果给出的数据是若干个斜率为 00 的直线,这样求两直线交点的时候会出现除以 00 的情况,导致没有任何输出,趋势也就是必然的了。
正确解答是可以在前面加上特判的东西,也不影响复杂度。

    bool flag=1;
    int maxid=1;
    for(int i=1;i<=n;i++)
    {
        if(f[i].a!=0)
        {
            flag=0;
            break;
        }
        if(f[maxid].b<f[i].b)
        {
            maxid=i;
        }
    }
    if(flag)
    {
        write(maxid);
        return putchar(10),0;
    }

乐:)

2024/10/18 10:54
加载中...