【USACO】奶牛跑步2

P1443 - 【USACO】奶牛跑步2

Description

FJ的N(1 <= N <= 100,000)头奶牛们又兴高采烈地出来运动了！她们在一条无限长的小路上跑步，每头牛起跑的位置都不同，速度也不尽相同。
道路中划出了若干条跑道，以便她们能快速"超车"，同一跑道中的任意两头牛都不会出现在相同的位置。不过FJ不愿让任何一头牛更换跑道或者调整速度，他想知道如果让牛们跑足T(1 <= T <= 1,000,000,000)分钟的话，至少需要多少条跑道才能满足需要。

Input

第一行有两个数，N和T;
接下来有N行，每一行两个数，表示一头牛的位置和速度，其中位置是一个非负整数，速度为一个正整数，均不超过10^9。所有牛的开始位置均不相同，因此N头牛的数据将以位置升序的方式给出。

Output

输出为一个整数，表示所需跑道的最小数目，要保证同一跑道中的任意两头牛在T时限内（到第T分钟结束）不会撞到一起。

Sample Input

Sample Output

3

因为数据所给的起点是升序的，所以可以推出：

当s2+t*v2<=s1+t*v1时，２和１不能在同一跑道。

所以就可以把每个点的s+v*t算出来，从后往前扫，先查询有没有比这个数大的数，若没有则答案＋１，否则要删去比这个数大的一个数，注意是一个数，我一开始把它们全删了导致ＷＡ飞。

然后问题是要删哪一个数，贪心地想想，肯定是删最小的那个最优，这样就可以保证大的数可以被另外的数删。

  1 #include<set>
  2 #include<map>
  3 #include<queue>
  4 #include<stack>
  5 #include<ctime>
  6 #include<cmath>
  7 #include<string>
  8 #include<vector>
  9 #include<cstdio>
 10 #include<cstdlib>
 11 #include<cstring>
 12 #include<iostream>
 13 #include<algorithm>
 14 #define maxn 100010
 15 #define LL long long
 16 #define inf 999999999999999995ll
 17 using namespace std;
 18 int ch[maxn][2],pre[maxn],size[maxn],root=0,tot=0;
 19 LL ANS=0,key[maxn],in[maxn];
 20 void updata(int x){
 21   size[x]=size[ch[x][0]]+size[ch[x][1]]+1;
 22 }
 23 void Rotate(int x,int kind){
 24   int y=pre[x];
 25   ch[y][!kind]=ch[x][kind];
 26   pre[ch[x][kind]]=y;
 27   if(pre[y])
 28     ch[pre[y]][ch[pre[y]][1]==y]=x;
 29   pre[x]=pre[y];
 30   ch[x][kind]=y;
 31   pre[y]=x;
 32   updata(y);
 33   updata(x);
 34 }
 35 void Splay(int r,int goal){
 36   while(pre[r]!=goal){
 37     if(pre[pre[r]]==goal)
 38       Rotate(r,ch[pre[r]][0]==r);
 39     else{
 40       int y=pre[r];
 41       int kind=ch[pre[y]][0]==y;
 42       if(ch[y][kind]==r){
 43     Rotate(r,!kind);
 44     Rotate(r,kind);
 45       }
 46       else{
 47     Rotate(y,kind);
 48     Rotate(r,kind);
 49       }
 50     }
 51   }
 52   if(goal==0) root=r;
 53 }
 54 void newnode(int &x,int fa,LL keyy){
 55   x=++tot;
 56   pre[x]=fa;
 57   ch[x][0]=ch[x][1]=0;
 58   key[x]=keyy;
 59   size[x]=1;
 60 }
 61 void Insert(LL k){
 62   while(ch[root][key[root]<k])
 63     size[root]++,root=ch[root][key[root]<k];
 64   size[root]++;
 65   newnode(ch[root][key[root]<k],root,k);
 66   Splay(ch[root][key[root]<k],0);
 67 }
 68 void get_nex(int x,LL k,int &ans){
 69   if(!x) return;
 70   if(key[x]<=k) ans=x,get_nex(ch[x][1],k,ans);
 71   if(key[x]>k) get_nex(ch[x][0],k,ans);
 72 }
 73 void erase(int x){
 74   int nexx=ch[x][1];
 75   while(ch[nexx][0]) nexx=ch[nexx][0];
 76   Splay(nexx,0);
 77   if(!ch[nexx][1]) pre[ch[nexx][0]]=0,root=ch[nexx][0];
 78   else{
 79     pre[ch[nexx][1]]=0;
 80     int rt=ch[nexx][1];
 81     while(ch[rt][0]) rt=ch[rt][0];
 82     pre[ch[nexx][0]]=rt;
 83     ch[rt][0]=ch[nexx][0];
 84   }
 85 }
 86 void solve(LL k){
 87   int nex1=root;get_nex(root,k,nex1);
 88   Splay(nex1,0);
 89   if(!size[ch[nex1][1]])
 90     ANS++;
 91   else erase(nex1);
 92   updata(nex1);
 93 }
 94 int main()
 95 {
 96   freopen("!.in","r",stdin);
 97   freopen("!.out","w",stdout);
 98   int n;
 99   LL v,t;
100   scanf("%d%lld",&n,&t);
101   for(int i=1;i<=n;i++)
102     scanf("%lld%lld",&in[i],&v),in[i]+=v*t;
103   newnode(root,0,-inf);
104   for(int i=n;i>=1;i--){
105     solve(in[i]);
106     Insert(in[i]);
107   }
108   printf("%lld
",ANS);
109   return 0;
110 }