自动搬运

查看原文

来自洛谷，原作者为

	hht2005 这个家伙很菜，什么也没有留下

搬运于2025-08-24 22:04:48，当前版本为作者最后更新于2019-02-06 21:29:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这一题的本质其实是求牛结束位置的最长不上升子序列，其他一些篇题解都说了，但没说为什么，我在这可以给出两种有证明的思路。

思路1

对于两头牛，A牛和B牛，如果A牛超过了B牛，则说明A牛初始位置<=B牛初始位置且A牛结束位置>=B牛结束位置。在这种情况下，它们需要两条跑道。

同样的，如果有k头牛，第一头牛超过第二头牛，第二头牛超过第三头牛……，则说明它们的初始位置是不下降的，结束位置是不上升的。在这种情况下，它们需要k条跑道。

对于n头牛，问它们最少需要多少跑道，其实就是能满足初始位置不下降，结束位置不上升最多能选出多少头牛。由于输入以按照升序，所以我们只要考虑结束位置就行。不上升+最长=最长不上升子序列。

思路2 对于两头牛，A牛和B牛，如果A牛和B牛可以在同一条跑道上，则说明A牛初始位置<=B牛初始位置且A牛结束位置<=B牛结束位置，或A牛初始位置>=B牛初始位置且A牛结束位置>=B牛结束位置。

同样的，如果有k头牛，将它们按初始位置升序排列，如果它们可以在同一条跑道上，则说明它们结束位置也是升序的。

于是，题目就变成了求牛的结束位置最少能被分成多少个上升序列，就是Noip1999导弹拦截的第二问。当然，此题需要用nlogn的算法。但导弹拦截第二问的高效算法其实就是最长不上升子序列。

code：

两个思路代码都一样。

#include<iostream>
#include<algorithm>
using namespace std;
long long a[100010],c[100010],top,n,t;//会爆int
int main()
{
    long long p,v;
    scanf("%lld%lld",&n,&t);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld%lld",&p,&v);
        a[i]=p+v*t;//计算结束位置
    }
    for(int i=n;i>=1;i--)//倒过来变成最长不下降子序列，可以用upper_bound。
    {
        if(!top||a[i]>=c[top])
            c[++top]=a[i];
        else
        {
            int t=upper_bound(c+1,c+top+1,a[i])-c;
            c[t]=a[i];
        }
    }
    printf("%lld\n",top);
}