关键词：
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
5 3
0 1
1 2
2 3
3 2
6 1
Sample Output
3
Hint
Source
USACO
基本 ，平衡树
首先得到一个式子，xi+vi*T < xj+vj*T,若j与i满足这个条件，则j可以放在i后面，与i用一个跑道，意思是i无论如何都无法再T时间内追上j。但有很多个点满足，因为把j放入跑道之后，这条跑道的条件就要用j的信息来判断了，所以要使损失最小，则应该把j放到所有满足条件的值最大的那个后面，所以此时应该贪心一个一个的加入，用平衡树来实现查找，然后删除这个前驱，加入这个点。若没有前驱则表示没有满足条件的，需增加一个跑道，此时ans++;
1 #include<map> 2 #include<set> 3 #include<cmath> 4 #include<ctime> 5 #include<queue> 6 #include<stack> 7 #include<cstdio> 8 #include<vector> 9 #include<cstdlib> 10 #include<cstring> 11 #include<iomanip> 12 #include<iostream> 13 #include<algorithm> 14 #define ll long long 15 #define rep(i,a,b) for(register int i=a;i<=b;i++) 16 #define re register 17 #define il inline 18 using namespace std; 19 const int N=100010; 20 int pre[N],cnt[N],ch[N][2],n,root,tot; 21 ll key[N],T; 22 il ll gl() { 23 ll ret=0;char ch=getchar(); 24 while(ch<‘0‘||ch>‘9‘) ch=getchar(); 25 while(ch>=‘0‘&&ch<=‘9‘) ret=ret*10+ch-‘0‘,ch=getchar(); 26 return ret; 27 } 28 il int getx(int x) {return ch[pre[x]][1] == x;} 29 il void Newnode(int fa,ll v) { 30 ++tot; 31 pre[tot]=fa , cnt[tot]=1; 32 key[tot]=v; 33 } 34 il void Rotate(int x) { 35 int old=pre[x],oldx=pre[old],bj=getx(x); 36 ch[old][bj]=ch[x][!bj];pre[ch[old][bj]]=old; 37 ch[x][!bj]=old;pre[old]=x; 38 pre[x]=oldx; 39 if(oldx) ch[oldx][ch[oldx][1]==old]=x; 40 } 41 il void Splay(int x,int goal) { 42 while(pre[x]!=goal) { 43 if(pre[pre[x]]==goal) Rotate(x); 44 else { 45 int no=getx(x),od=getx(pre[x]); 46 if(no==od) Rotate(pre[x]),Rotate(x); 47 else Rotate(x),Rotate(x); 48 } 49 } 50 if(goal==0) root=x;// bug 51 } 52 il void Insert(ll v) { 53 if(root==0) { 54 Newnode(0,v);root=tot;return; 55 } 56 int now=root,fa=0; 57 while(1) { 58 if(key[now]==v) { 59 cnt[now]++;Splay(now,0);return; 60 } 61 fa=now; 62 now=ch[now][v > key[now]]; 63 if(now==0) { 64 Newnode(fa,v); 65 ch[fa][v > key[fa]] = tot; 66 Splay(tot,0); 67 return; 68 } 69 } 70 } 71 il int get_pre() { 72 int now=ch[root][0]; 73 while(ch[now][1]) now=ch[now][1]; 74 return now; 75 } 76 il void del(int x) { 77 if(root==0) return; 78 Splay(x,0); 79 if(cnt[x]>1) {cnt[x]--;return;} 80 if(!ch[x][0]&&!ch[x][1]) { 81 root=0;return; 82 } 83 if(!ch[x][0]) { 84 root=ch[x][1];pre[root]=0; 85 return; 86 } 87 else if(!ch[x][1]) { 88 root=ch[x][0];pre[root]=0; 89 return; 90 } 91 int l=get_pre(); 92 Splay(l,0);// 93 ch[root][1]=ch[x][1]; 94 pre[ch[x][1]]=root;// bug 95 ch[x][1]=ch[x][0]=cnt[x]=0;// 96 return; 97 } 98 int find(ll k) {// 找到 <= k 的最大数 99 int ret=-1,now=root; 100 while(now) { 101 if(key[now] < k) ret=now,now=ch[now][1]; 102 else now=ch[now][0]; 103 } 104 return ret; 105 } 106 int main() { 107 scanf("%d",&n);T=gl(); 108 re ll x,v,S; 109 int ans=0; 110 rep(i,1,n) { 111 x=gl(),v=gl(),S=x+v*T; 112 int cur=find(S); 113 if(cur==-1) ans++; 114 else del(cur); 115 Insert(S); 116 } 117 cout<<ans; 118 return 0; 119 }
cogs1945.奶牛跑步
...对比时间限制：1s 内存限制：256MB【题目描述】奶牛们又兴高采烈地出去运动了！一共有N(1<=N<=100,000)头牛在一条无限长的单向羊肠小道上慢跑。每头牛在小道上的起点都不同，牛儿们的速度也不尽相同。这条羊肠小... 查看详情
dp专题
一、奶牛的锻炼(exer.c/.cpp/.pas)Description:奶牛Bessie有N分钟时间跑步，每分钟她可以跑步或者休息。若她在第i分钟跑步，可以跑出D_i米，同时疲倦程度增加1（初始为0）。若她在第i分钟休息，则疲倦程度减少1。无论何时，疲倦程度... 查看详情
18.12.20poj3661跑步(代码片段)
描述奶牛们打算通过锻炼来培养自己的运动细胞，作为其中的一员，贝茜选择的运动方式是每天进行N(1<=N<=10,000)分钟的晨跑。在每分钟的开始，贝茜会选择下一分钟是用来跑步还是休息。贝茜的体力限制了她跑步的距离。更... 查看详情
[dp]tvvj1023奶牛的锻炼
思考首先鄙人在这个题目上面思考的状态方程是dp[i][1]表示第i分钟能跑的情况下最大路程dp[i][0]表示第i分钟不能跑情况下的最大路程。但是在思考片刻之后发现有疲劳度的限制，所以这个方程没有办法产生联系。在思考许久无果... 查看详情
笔试算法题目，奶牛排队喝水
题目：题目描述 有N(1≤N≤1000)头奶牛，它们都被标上一个优先等级编号：1，2或3。用来表示它们喝水时的优先次序，编号为l的最优先，编号为2的其次，编号为3的最后。每天奶牛开始时排成一行，但总是很乱，需要你把它们... 查看详情
bzoj2199[usaco2011jan]奶牛议会2-sat
【BZOJ2199】[Usaco2011Jan]奶牛议会Description由于对FarmerJohn的领导感到极其不悦，奶牛们退出了农场，组建了奶牛议会。议会以“每头牛都可以获得自己想要的”为原则，建立了下面的投票系统：M只到场的奶牛(1<=M<=4000)会... 查看详情
排序奶牛的编号(代码片段)
题目描述有N(1≤N≤1000)头奶牛，它们都被标上一个优先等级编号：1，2或3。用来表示它们喝水时的优先次序，编号为l的最优先，编号为2的其次，编号为3的最后。每天奶牛开始时排成一行，但总是很乱，需要你把它们重新排成... 查看详情
跑步书籍推荐---跑步指南
1.跑步指南跑步指南 著出版社：机械工业出版社出版时间：2015-08-01ISBN：9787111514084这本书个人推荐，图文讲解，非常适合入门，很不错的书籍 2.不跑会死：中国跑步指南宋歌编著北京：煤炭工业出版社出版时间：2014-07-... 查看详情
奶牛渡河——线性dp(代码片段)
奶牛渡河——线性dp题目描述FarmerJohn以及他的N(1<=N<=2,500)头奶牛打算过一条河，但他们所有的渡河工具，仅仅是一个木筏。由于奶牛不会划船，在整个渡河过程中，FJ必须始终在木筏上。在这个基础上，木筏上的奶牛数目每... 查看详情
bzoj2199/usaco2011jan奶牛议会——2-sat
Description由于对FarmerJohn的领导感到极其不悦，奶牛们退出了农场，组建了奶牛议会。议会以“每头牛都可以获得自己想要的”为原则，建立了下面的投票系统：M只到场的奶牛(1<=M<=4000)会给N个议案投票(1<=N<=1,000)。... 查看详情
bzoj1613贝茜的晨练计划(代码片段)
Description奶牛们打算通过锻炼来培养自己的运动细胞，作为其中的一员，贝茜选择的运动方式是每天进行N(1<=N<=10,000)分钟的晨跑。在每分钟的开始，贝茜会选择下一分钟是用来跑步还是休息。贝茜的体力限制了她跑步的距离... 查看详情
poj3180奶牛舞会
题目大意： 约翰的N(2≤N≤10000)只奶牛非常兴奋，因为这是舞会之夜！她们穿上礼服和新鞋子，别上鲜花，她们要表演圆舞。 只有奶牛才能表演这种圆舞．圆舞需要一些绳索和一个圆形的水池．奶牛们围在池边站好，顺... 查看详情
记忆化搜索游荡的奶牛
[luogu1535]游荡的奶牛题目描述Searchingfortheverybestgrass,thecowsaretravellingaboutthepasturewhichisrepresentedasagridwithNrowsandMcolumns(2<=N<=100;2<=M<=100).KeenobserverFarmerJohnhasrecordedBess 查看详情
2020.07.16模拟2(代码片段)
A.Layout题目描述和人类一样，奶牛们在打饭的时候喜欢和朋友站得很近。约翰的编号为1到n的n只奶牛正打算排队打饭。现在请你来安排她们，让她们在数轴上排好队。奶牛的弹性很好，同一个坐标可以站无限只奶牛，排队的顺序... 查看详情
奶牛排序——rmq(代码片段)
【问题描述】奶牛在熊大妈的带领下排成了一条直队。显然，不同的奶牛身高不一定相同……现在，奶牛们想知道，如果找出一些连续的奶牛，要求最左边的奶牛A是最矮的，最右边的B是最高的，且B高于A奶牛，且中间如果存在... 查看详情
洛谷p1535游荡的奶牛(代码片段)
P1535游荡的奶牛题目描述Searchingfortheverybestgrass,thecowsaretravellingaboutthepasturewhichisrepresentedasagridwithNrowsandMcolumns(2<=N<=100;2<=M<=100).KeenobserverFarmerJohnhasrecordedBessie‘spo 查看详情
p2837晚餐队列安排
...背景UsacoFeb08Bronze题目描述为了避免餐厅过分拥挤，FJ要求奶牛们分2批就餐。每天晚饭前，奶牛们都会在餐厅前排队入内，按FJ的设想，所有第2批就餐的奶牛排在队尾，队伍的前半部分则由设定为第1批就餐的奶牛占据。由于奶牛... 查看详情
题解幸运奶牛(代码片段)
题目描述 有N头奶牛从左往右排成一行，编号是1至N。如果某头奶牛的编号是2的倍数或者是3的倍数，那么这头奶牛就是幸运奶牛。这N头奶牛中，总共有多少头奶牛是幸运奶牛？ 输入输出格式输入格式 &nb... 查看详情