bzoj3190 [JLOI2013] 比赛
最编程
2024-04-03 22:29:01
...
bzoj3190[JLOI2013]赛车
题意:
赛场上一共有N辆车。赛道是一条无限长的直线。在这个比赛过程中,如果一辆赛车曾经处于领跑位置的话(即没有其他的赛车跑在他的前面),这辆赛车最后就可以得奖。已知所有赛车的起始位置(离起跑线距离)和速度,求出那些赛车将会得奖。
题解:
有人说是类似线性规划,用半平面交,反正我不会,数学考试是线性规划也错得一塌糊涂QAQ。
黄学长用的是维护斜率的方法,按照斜率排个序,依次插入一个单调栈,如果栈顶不满足XX条件(说不清楚,画个图)就弹掉,最后留在栈里的就是答案。
代码:
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 #define inc(i,j,k) for(int i=j;i<=k;i++) 5 #define eps 1e-8 6 using namespace std; 7 8 struct nd{ 9 int s,v,id; 10 bool operator < (const nd& a)const{ 11 if(v!=a.v)return v<a.v; return s<a.s; 12 } 13 }; 14 double solve(nd a,nd b){ 15 return (double)(a.s-b.s)/(double)(b.v-a.v); 16 } 17 nd nds[20000],s[20000]; int ans[20000],n,tp; 18 int main(){ 19 scanf("%d",&n); inc(i,1,n)scanf("%d",&nds[i].s),nds[i].id=i; inc(i,1,n)scanf("%d",&nds[i].v); sort(nds+1,nds+1+n); 20 tp=1;s[tp]=nds[1];ans[tp]=nds[1].id; 21 inc(i,2,n){ 22 while(tp>=1&&solve(s[tp],nds[i])<-eps)tp--; 23 while(tp>=2&&solve(s[tp-1],s[tp])>solve(s[tp],nds[i]))tp--; 24 s[++tp]=nds[i]; ans[tp]=nds[i].id; 25 } 26 sort(ans+1,ans+1+tp); printf("%d\n",tp); 27 inc(i,1,tp){ 28 i==tp?printf("%d",ans[i]):printf("%d ",ans[i]); 29 } 30 return 0; 31 }
20160407
推荐阅读
-
2019 年个人训练比赛 - F - 两小串
-
C++ Notes 打卡日 24(演讲比赛流程管理系统)
-
????2022 年年终总结征文比赛和 "吐槽 "活动正在进行中!吐出不快,展望未来!
-
人工智能赢得德州扑克比赛的背后,《自然》总结了最受关注的九大问题
-
数据包络分析(DEA)详解(基于第八届宁夏省级比赛)
-
Eagle Noble Technology 无人机课程、无人机比赛、无人机培训:青少年无人机初级竞赛课程介绍
-
dijkstra + dp, PTA *比赛练习套装 L2-001 紧急救援
-
蓝桥杯 [第 15 届省级比赛] Python B 组
-
苏州,遇见恩智浦痞子恒--刚下高铁比较累 "飞机、高铁、打车、打车、打车",加上这些年运动机能下降,身体状态比不上年轻的时候,但是一到打球的时候,我就很兴奋,我喜欢呆在球场上的感觉,这种感觉跟着我的体力走,我有体力的时候,我就想在球场上大杀四方,我没有体力的时候,我就想回家睡觉。没有体力的时候,我就想回家睡觉。 今天的比赛很激烈,恩智浦的年轻球员有那么一点凶,我本来是想过来打酱油的,但实际情况是他们在不停地搓我的老腰,晚上我发了一张比赛的照片,一个微信好友私聊我说了下面的话。 大家自己体会,我觉得有人在针对我的腰,????。 痞子恒打得很好,中投和突破上篮技术很娴熟,有几次上篮我觉得很勉强,但球还是往篮筐里面进,可能是这种同是天涯沦落人的情怀,让我喜欢上了这个同龄的小伙子,做技术很好,打球也很好,待人很体贴????。 比赛结束后,痞子恒带我们去吃烧烤,因为太累了,胃口不是很好,只能看着肉叹气,不过吃饭的时候听大家聊天的感觉还是很不错的,让我知道了苏州的工作和生活节奏。 晚上回到宾馆,何先生说:"这就是他们的生活啊,让我感慨万千"。 我跑了三千多里路,就是为了来这里玩游戏,说出来你可别笑! ---- 痞子衡嵌入式公共号文章汇总
-
祖国在我心中 "书法比赛获奖者