题目描述

Description

Farmer John's N cows (1 <= N <= 100,000) are out exercising their hooves again, jogging along an infinite track. Each cow starts at a distinct position on the track, and some cows run at different speeds. The track is divided into lanes so that cows may move past each other. No two cows in the same lane may ever occupy the same position. Farmer John doesn't want any cow to have to change lanes or adjust speed, and he wonders how many lanes he will need to accomplish this if the cows are going to run for T minutes (1 <= T <= 1,000,000,000).
给出N头牛，每头牛有自己的初始位置及奔跑的速度。它们要跑T分钟，现在不希望他们的跑的过程中出现“撞车”即跑到同一个点上，因而要将道路分成若干个跑道，问至少要多少个跑道。

Input

The first line of input contains N and T. The following N lines each contain the initial position and speed of a single cow. Position is a nonnegative integer and speed is a positive integer; both numbers are at most 1 billion. All cows start at distinct positions, and these will be given in increasing order in the input.

Output

A single integer indicating the minimum number of lanes necessary so that no two cows in the same lane ever occupy the same location (including at time T).

Sample Input

5 3
0 1
1 2
2 3
3 2
6 1

Sample Output

3

题目分析

将每个牛的权值看为：位置+速度*时间
问题本质：给你一个序列 要求用最少的上升子序列来覆盖整个序列
= =这竟然是一个结论题 我一开始以为只是离散化+求序列的逆序对 结果我发现自己naive了
= =答案就是序列最长不下上升的子序列长度
具体证明好像是要证明可以用最少链覆盖=最长反链 也就是最大独立集
使用二分进行优化

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
long long a[100010],f[100010];
int k;
int fen(long long tmp)
{
    int l,r,mid;
    l=1;
    r=k;    
    while(l<r)
    {
        mid=(l+r)>>1;
        if(tmp<f[mid]) l=mid+1;
        else if(tmp>f[mid])r=mid;  
        else return mid;
    } 
    return l;
}
long long t;
int main()
{
    int n;
    scanf("%d%lld",&n,&t);
    for(int i=1;i<=n;i++)
    {
        long long x,y;
        scanf("%lld%lld",&x,&y);
        a[i]=x+t*y;
    }
    f[1]=a[1];
    k++;
    for(int i=2;i<=n;i++)
    {
        if(a[i]<=f[k])  f[++k]=a[i];
        else if(a[i]>f[k]) f[fen(a[i]-1)]=a[i];
    }
    printf("%d",k);
}