前言

此题在测评网站上找不到原题，仅供想学习单调数组的同学们交流使用。

对单调队列（单调数组）没有了解的可以看看这篇博客。

题面

3041: 奶牛慢跑

题目描述

有n（n<=100000）头奶牛在一个无穷长的小道上慢跑。每头奶牛的起点不同，速度也不同。小道可以被分成多条跑到。奶牛只能在属于自己的跑道上慢跑，不允许更换跑道，也不允许改变速度。如果要慢跑t（t<=1000000000）分钟，要保证在任何时候不会有同一跑道上的奶牛相遇，请问最少需要多少条跑道。奶牛开始在哪条跑道是可以随意设置的。

输入

输入格式：第一行两个整数n，t。

接下来的n行，每行包含两个整数，表示奶牛的位置和速度。位置是非负整数，速度是正整数。所有的奶牛的起点都不相同，按起点递增的顺序给出。

输出

输出格式：

最少的跑道数。

样例输入

5 3

0 1

1 2

2 3

3 2

6 1

样例输出

3

分析

此题要我们求需要多少根跑道，也就是让我们把一些奶牛合并起来，它们的起点不同，并且T分钟后不会相遇。（相遇的意思就是一头奶牛把另一头奶牛追上了，也就是追及问题）举个例子，如果时间为t，第i头奶牛的起点为s[i],速度为v[i],如果i和j这两头奶牛要在同一根跑道(s[i]所有的奶牛的起点都不相同，按起点递增的顺序给出。”根据上述构造的结构，起点是s[i],这头牛到终点的路程是z[i](s[i]+t*v[i])可以求出来,因为起点是递增的（也就是s[1]

注：此题数据过大，普通DP就最长下降子序列会超时，应该用单调数组进行优化，代码如下。

代码

#include

#include

using namespace std;

#define N 100010

#define LL long long

#define inf 0x7f7f7f7f7f7f

int read() {

int f=1,s=0;char a=getchar();

while(!(a>='0'&&a<='9')) {if(a=='-') f=-1 ; a=getchar(); }

while(a>='0'&&a<='9') {s=s*10+a-'0'; a=getchar();}

return f*s;

}

LL n,a[N],t,k=0;

int main()

{

n=read();

t=read();

a[0]=1ll<<60;

for(int i=1;i<=n;i++) {

LL p=read(),q=read(),sum;

sum=p+1ll*t*q;//计算奶牛的终点距离

if(sum<=a[k]) {//维护单调数组，看不懂的可以看看我的导弹拦截，这里不再赘述

a[++k]=sum;

continue;

}

int l=0,r=k,mid;

while(l

mid=(l+r+1)/2;

if(sum>a[mid]) r=mid-1;

else l=mid;

}

a[l+1]=sum;

}

cout<

return 0;

}

后记

此题代码的主题就是最大下降子序列，并进行了变形。我们做题时，也要从本质出发，而不是盲目地“打爆搜”。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!