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

概述本文章向大家介绍C++巧妙运用单调数组解题——奶牛慢跑（Cow Jogging），主要包括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]

注：此题数据过大，普通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;

}

后记

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

总结

以上是内存溢出为你收集整理的C++巧妙运用单调数组解题——奶牛慢跑（Cow Jogging）全部内容，希望文章能够帮你解决C++巧妙运用单调数组解题——奶牛慢跑（Cow Jogging）所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。