题目描述
有n（n<=100000）头奶牛在一个无穷长的小道上慢跑。每头奶牛的起点不同，速度也不同。小道可以被分成多条跑到。奶牛只能在属于自己的跑道上慢跑，不允许更换跑道，也不允许改变速度。如果要慢跑t（t<=1000000000）分钟，要保证在任何时候不会有同一跑道上的奶牛相遇，请问最少需要多少条跑道。奶牛开始在哪条跑道是可以随意设置的。
输入
输入格式：第一行两个整数n，t。
接下来的n行，每行包含两个整数，表示奶牛的位置和速度。位置是非负整数，速度是正整数。所有的奶牛的起点都不相同，按起点递增的顺序给出。
输出
输出格式：
最少的跑道数。
样例输入
5 3
0 1
1 2
2 3
3 2
6 1
样例输出
3解题思路
要想要求出正确的答案，其实就必须要想到题目中的性质，打出合适的算法。我们不看每一头牛当前的速度与位置，因为这样计算将会十分复杂，我们首先就必须要求出它们在最后的时候到达了哪里，这样，逆序的中途即会相遇。
那么如何求出最少需要的跑道个数呢？考试的时候呢，我是这样想的，每一个跑道都是上升的子序列，那么就一定满足条件，这样求出最小，其实再想一想，如果求出了最长不上升子序列，不就可以得出答案了吗？最长不上升子序列中的元素任意两两一定会相遇的。因此，它们都需要单独一个跑道，而其他的呢就无所谓了。
因此，这道题就是求一个最长不上升子序列，相信这种DP题目大家都会，但朴素的DP算法时间复杂度是N方的，此题是过不了的。那么关键就是要看如何进行优化了。如果大家看过一些书籍，应该对于运用lower_bound函数进行二分优化的最长不下降子序列有一定印象。确实，这道题可以说就是运用二分进行优化。
二分要满足单调性，因此我们需要排序。
之后，将数组中的数一一进行二分，找到合适位置而放进去，保持数组呈不上升。
这里估计有人会有疑问了，为什么这样就真能保证数组合理呢？首先，最长肯定是对的，我们可以很轻松判断出来，但是否真的存在这样的序列呢？
我们给出简单的一些数据进行讨论 如（3 ， 2 ， 8） ，处理完后，就变成了（ 8 ， 2）。很显然，这一种数列是不存在的。
但我们再看一下，它的长度并没有变化。最长不下降子序列的长度的确是数组的长度2。
那么再在后面加一些数据？ （3 ， 2 ， 8 ，1） ， 处理完后，变成了 （ 8 ，2 ， 1）。这种数列更奇怪了，然而，答案却还是这么多。其实，将8放入队头，我们可以看出这可能是一个更有用的数字，因为它大，所以后面空间可能更大。而放入队头，虽然看起来不合理，但并不会改变答案的最优性质。
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<vector>
#include<stack>
using namespace std;
#define LL long long
#define N 100005
struct node {
long long x;
int id;
}a[N];
int n,len = 1;
long long maxt , dp [N],t;
int read(){
int f = 1 , x = 0;
char s = getchar();
while (s < '0' || s > '9'){
if (s == '-')
f = -1;
s = getchar();
}
while (s >= '0' && s <= '9'){
x = x * 10 + s - '0';
s = getchar();
}
return f * x;
}
int solve(long long x){//二分求解
int l = 1 ,r = len + 1;
while (l + 1 < r){
int mid = (l + r)/ 2;
if (dp[mid] >= x){
l = mid;
}
else
r = mid;
}
if (dp[l] < x)
return l;
else
return r;
}
int main(){
// freopen("shuju.in","r",stdin);
n = read();
t = read();
for (int i = 1;i <= n ;i ++ ){
a[i].id = i;
long long t1 = read();
long long q = read();
a[i].x = 1ll * t1 + 1ll * q * t ;//求出终点
maxt = max (a[i].x , maxt);//确定r范围
}
dp[1] = a[1].x;
for (int i = 2 ;i <= n; i ++ ){//将数组每一个都进行处理
if (dp[len] >= a[i].x) {
dp[++ len] = a[i].x;
continue;
}
else{
int j = solve(a[i].x);
dp[j] = a[i].x;
len = max(len,j);
}
}
printf("%d",len);
}总结
考试的时候，确实没有看出这道题的性质，当时却也是想到了最长不上升子序列，但总觉得这样的做法不是最优，至于为什么，我也不知道。。。考试的时候，我觉得这道题就像是递归求出每一个最长不下降子序列，其实如果我再细细想想的话，这道题不就是求一个最长不上升子序列吗？主要还是被第一题困扰了，打乱了后面所有题的进度。