正文

usaco奶牛跑步2

蒟蒻ZJO:-)  蒟蒻ZJO:-)  2022-08-27  240

关键词：

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 }

bzoj2199[usaco2011jan]奶牛议会2-sat

【BZOJ2199】[Usaco2011Jan]奶牛议会Description由于对FarmerJohn的领导感到极其不悦，奶牛们退出了农场，组建了奶牛议会。议会以“每头牛都可以获得自己想要的”为原则，建立了下面的投票系统：M只到场的奶牛(1<=M<=4000)会... 查看详情

bzoj2199/usaco2011jan奶牛议会——2-sat

Description由于对FarmerJohn的领导感到极其不悦，奶牛们退出了农场，组建了奶牛议会。议会以“每头牛都可以获得自己想要的”为原则，建立了下面的投票系统：M只到场的奶牛(1<=M<=4000)会给N个议案投票(1<=N<=1,000)。... 查看详情

奶牛接力(cowrelays,usaco2007nov)

题目描述Fortheirphysicalfitnessprogram,N(2≤N≤1,000,000)cowshavedecidedtorunarelayraceusingtheT(2≤T≤100)cowtrailsthroughoutthepasture.Eachtrailconnectstwodifferentintersections(1≤I1i≤1,000;1≤I2i≤1,000),eac 查看详情

bzoj1703[usaco2007mar]rankingthecows奶牛排名*

bzoj1703[Usaco2007Mar]RankingtheCows奶牛排名题意：n头奶牛，知道n对奶牛之间的产奶量大小，问想知道所有奶牛产奶量大小顺序至少还需知道几对。n≤1000。题解：每个大小关系看为一条有向边，对每头奶牛进行dfs，求每头奶牛可以到... 查看详情

p2915[usaco08nov]奶牛混合起来mixedupcows(代码片段)

P2915[USACO08NOV]奶牛混合起来MixedUpCows约翰家有N<=16头奶牛，第i头奶牛的编号是Si，每头奶牛的编号都是唯一的。这些奶牛最近在闹脾气，为表达不满的情绪，她们在挤奶的时候一定要排成混乱的队伍。在一只混乱的队伍中，相邻... 查看详情

bzoj1655[usaco2006jan]dollardayz奶牛商店*

bzoj1655[Usaco2006Jan]DollarDayz奶牛商店题意：商场里有K种工具，价格分别为1，2，…，K美元。约翰手里有N美元，必须花完。求购买组合方案。n≤1000，k≤100。题解：完全背包，不过要高精度。代码：1#include<cstdio>2#include<cstring&... 查看详情

洛谷p1894[usaco4.2]完美的牛栏theperfectstall

...题，每个牛栏都不一样。第一个星期，农夫约翰随便地让奶牛们进入牛栏，但是问题很快地显露出来：每头奶牛都只愿意在她们喜欢的那些牛栏中产奶。上个星期，农夫约翰刚刚收集到了奶牛们的爱好的信息（每头奶牛喜欢在哪... 查看详情

洛谷p1894[usaco4.2]完美的牛栏theperfectstall

洛谷——p1894[usaco4.2]完美的牛栏theperfectstall

p1894[usaco4.2]完美的牛栏theperfectstall(代码片段)

p2915[usaco08nov]奶牛混合起来mixedupcows

题目描述约翰家有N头奶牛，第i头奶牛的编号是Si，每头奶牛的编号都是唯一的。这些奶牛最近在闹脾气，为表达不满的情绪，她们在挤奶的时候一定要排成混乱的队伍。在一只混乱的队伍中，相邻奶牛的编号之差均超过K。比如... 查看详情

bzoj1604:[usaco2008open]cowneighborhoods奶牛的邻居

【算法】并查集+平衡树+数学【题解】经典哈夫曼距离转切比雪夫距离。哈夫曼距离：S=|x1-x2|+|y1-y2|即：max(x1-x2+y1-y2,x1-x2-y1+y2,-x1+x2+y1-y2,-x1+x2-y1+y2)令X1=x1+y1,Y1=x1-y1，切比雪夫距离：S=max(|X1-X2|,|Y1-Y2|)。转化为查看详情

[usaco2006jan]dollardayz奶牛商店

Description约翰到奶牛商场里买工具．商场里有K(1≤K≤100).种工具，价格分别为1，2，…，K美元．约翰手里有N(1≤N≤1000)美元，必须花完．那他有多少种购买的组合呢？InputAsinglelinewithtwospace-separatedintegers:NandK.仅一行，输入N，K.Outpu... 查看详情

[bzoj]1616:[usaco2008mar]cowtravelling游荡的奶牛

1616:[Usaco2008Mar]CowTravelling游荡的奶牛TimeLimit: 5Sec MemoryLimit: 64MBSubmit: 1312 Solved: 736[Submit][Status][Discuss]Description奶牛们在被划分成N行M列(2<=N<=100 查看详情

题解p1894[usaco4.2]完美的牛栏theperfectstall(代码片段)

[usaco11jan]大陆议会thecontinentalcowngress_2-sat

...alCowngress_2-sat题意：由于对FarmerJohn的领导感到极其不悦，奶牛们退出了农场，组建了奶牛议会。议会以“每头牛都可以获得自己想要的”为原则，建立了下面的投票系统：M只到场的奶牛(1<=M<=4000)会给N个议案投票(1<=N<=1,0... 查看详情

[usaco2005dec]layout

题目描述当排队等候喂食时，奶牛喜欢和它们的朋友站得靠近些。FJ有N（2<=N<=1000）头奶牛，编号从1到N，沿一条直线站着等候喂食。奶牛排在队伍中的顺序和它们的编号是相同的。因为奶牛相当苗条，所以可能有两头或者更... 查看详情

[bzoj]1706:[usaco2007nov]relays奶牛接力跑

1706:[usaco2007Nov]relays奶牛接力跑TimeLimit: 5Sec MemoryLimit: 64MBSubmit: 707 Solved: 367[Submit][Status][Discuss]DescriptionFJ的N(2<=N<=1,000,000)头奶牛选择了接力跑查看详情