杭电1009题解

http://acm.hdu.edu.cn/showproblem.php?pid=6759
题意:是说给你很多个初始位置和加速度的机器人.然后问你有多少个机器人曾经拿过rk1,并列不算.
怎么写呢?首先我们应该知道,假如两条线重合.那么显然是不能作为答案的,我们要标记一下.对于每个机器人来说他们的运动轨迹都可以看成是一条一次函数.然后我们就可以发现很多性质了,解方程的性质.
画个图:

我们很容易发现,假如我们先拿起始坐标按p排序,维护一个栈,就可以作为答案,首先我们把第一条线的信息放入栈,然后假如a小于栈顶里面的a那么显然不可能成为rk1,因为你起点低,后劲少怎么可能当rk1(好像说的就是我.)假如a大于栈顶那么就有机会当rk1了,这时候我们需要判断一下了,判断什么呢?忘记说了,我们的栈是维护的一个当rk1最先时间的单调栈.判断就是看谁当rk1的时间更快,具体怎么看呢?没错就是看交点,假设当前栈头为top,那么它后面一个就是top-1,假设我当前的匹配到了第i条线,假如说i和top-1的交点的时间比top和top-1交点的时间要短,显然top是不可能成为rk1的.

代码如下:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e4+5;
struct vv{
    ll p,a;//起始坐标 加速度.
}v[N];

bool cmp(vv x,vv y)//优先p然后a
{
    if(x.p==y.p)    return x.a>y.a;
    else            return x.p>y.p;
}
stack<int>s;//定义rk1时间的单调栈
int mp[N];//标记那些没有价值的线段
int main()
{
    ll t,n,ans=0;
    while(scanf("%lld",&t)!=EOF)
    {
        while(t--)
        {
            ans=0;
            memset(mp,0,sizeof mp);
            scanf("%lld",&n);
            for(ll i=1;i<=n;i++)
            {
                scanf("%lld%lld",&v[i].p,&v[i].a);
            }//输入
            sort(v+1,v+1+n,cmp);//排序
            for(ll i=1;i<=n;i++)
            {
                if(v[i].p==v[i-1].p&&v[i].a==v[i-1].a)
                {
                    mp[i]=1;mp[i-1]=1;
                }
            }
            s.push(1);
            for(int i=2;i<=n;i++)
            {
                if(v[i].a<=v[s.top()].a) continue;
                while(s.size()>1)
                {
                    int temp=s.top();
                    s.pop();
                    int last=s.top();
                    double ti=(double)(v[i].p-v[last].p)/(double)(v[last].a-v[i].a);
                    double ts=(double)(v[temp].p-v[last].p)/(double)(v[last].a-v[temp].a);
                    if(ti>ts)
                    {
                        s.push(temp);
                        s.push(i);
                        break;
                    }
                }
                if(s.size()==1) {s.push(i);}
            }
            while(s.size())
            {
                if(!mp[s.top()]) ans++;
                s.pop();
            }
            printf("%lld\n",ans);
        }
    }
    return 0;
}