C# · 12月 19, 2021

C++巧妙运用单调数组解题——奶牛慢跑(Cow Jogging)

前言

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

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

题面

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[j]),那就应该满足s[i]+t*v[i]<s[j]+t*v[j],如果是大于等于的话,那就是说第i头牛把第j头牛追上了,也就是不满足这种情况;初始的结构已经构造好了,那么我们再来回顾题面,看见一条重要的信息“所有的奶牛的起点都不相同,按起点递增的顺序给出。”根据上述构造的结构,起点是s[i],这头牛到终点的路程是z[i](s[i]+t*v[i])可以求出来,因为起点是递增的(也就是s[1]<s[2]<s[3]….<s[n]),那么根据输入数据的顺序算出z[i],如果连续一段(z[i]~z[j])是满足上升的,那么它们一定可以放在同一根跑道上,也就是说,整个要求的跑道数量就是一个最长下降子序列(类似于导弹拦截)。那么具体的思路就出来了,就是要求出z[i],然后对z数组求一个最长下降子序列,下降的数量便是我们要求的答案

注:此题数据过大,普通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<r) {

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

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

else l=mid;

}

a[l+1]=sum;

}

cout<<k;

return 0;

}

后记

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