首页 > 代码库 > 【BZOJ3190】[JLOI2013]赛车 单调栈+几何
【BZOJ3190】[JLOI2013]赛车 单调栈+几何
【BZOJ3190】[JLOI2013]赛车
Description
这里有一辆赛车比赛正在进行,赛场上一共有N辆车,分别称为个g1,g2……gn。赛道是一条无限长的直线。最初,gi位于距离起跑线前进ki的位置。比赛开始后,车辆gi将会以vi单位每秒的恒定速度行驶。在这个比赛过程中,如果一辆赛车曾经处于领跑位置的话(即没有其他的赛车跑在他的前面),这辆赛车最后就可以得奖,而且比赛过程中不用担心相撞的问题。现在给出所有赛车的起始位置和速度,你的任务就是算出那些赛车将会得奖。
Input
第一行有一个正整数N表示赛车的个数。
接下来一行给出N个整数,按顺序给出N辆赛车的起始位置。
再接下来一行给出N个整数,按顺序给出N辆赛车的恒定速度。
Output
输出包括两行,第一行为获奖的赛车个数。
第二行按从小到大的顺序输出获奖赛车的编号,编号之间用空格隔开,注意最后一个编号后面不要加空格。
Sample Input
4
1 1 0 0
15 16 10 20
1 1 0 0
15 16 10 20
Sample Output
3
1 2 4
1 2 4
HINT
对于100%的数据N<=10000, 0<=ki<=10^9, 0<=vi<=10^9
题解:将所有车按速度从小到大排序,然后一个一个扔到单调栈里,每次新加入一个时判断能不能把之前的弹出去。弹出去的条件是1.速度比它大,起点比它远 或2.把它盖住了一部分,剩下的那部分已经被别的车盖住了。把它扔到栈里以后,在算一下它被之前的车盖住了多少即可
证明见这篇博客
#include <cstdio>#include <cstring>#include <algorithm>#include <iostream>using namespace std;int n;struct car{ int v,x,org; double cro;}p[10010];int s[10010],top,vis[10010];bool cmp(car a,car b){ if(a.v==b.v) return a.x<b.x; return a.v<b.v;}int main(){ scanf("%d",&n); int i; for(i=1;i<=n;i++) scanf("%d",&p[i].x); for(i=1;i<=n;i++) scanf("%d",&p[i].v),p[i].org=i; sort(p+1,p+n+1,cmp); top=0; for(i=1;i<=n;i++) { while(top) { if(p[i].x>p[s[top]].x) top--; else if(1.0*p[s[top]].x-p[i].x<p[s[top]].cro*(p[i].v-p[s[top]].v)) top--; else break; } if(top&&p[i].v>p[s[top]].v) p[i].cro=(double)(p[s[top]].x-p[i].x)/(p[i].v-p[s[top]].v); s[++top]=i; } printf("%d\n",top); for(i=1;i<=top;i++) vis[p[s[i]].org]=1; int flag=0; for(i=1;i<=n;i++) { if(vis[i]) { if(flag) printf(" "); printf("%d",i); flag=1; } } return 0;}
【BZOJ3190】[JLOI2013]赛车 单调栈+几何
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。