NOIP模拟赛D2T1自己的解题思路
程序员文章站
2022-03-10 15:10:07
T1题目在此: 数轴上有n个球,每个球直径为1,第 ii 个球的左端点为pi即占据了数轴上[pi,pi+1][pi,pi+1])。在 P位置有一堵墙。有q个操作,每次要么以x位置为左端点放一个新球(如果有了就不管),要么把最左边的球往右推。一个球碰到另一个的时候,旧球停下来,新球继续滚。球碰到墙的时 ......
t1题目在此:
数轴上有n个球,每个球直径为1,第 ii 个球的左端点为pi即占据了数轴上[pi,pi+1][pi,pi+1])。在 p位置有一堵墙。
有q个操作,每次要么以x位置为左端点放一个新球(如果有了就不管),
要么把最左边的球往右推。一个球碰到另一个的时候,旧球停下来,新球继续滚。球碰到墙的时候就停下来。
最后你需要输出所有球的位置。
然后开始想:我的妈这不是一道水题么;然后用笔推算了一阵子,得出自己的结论:
链表可以快速插入一个元素;
为了快速放入元素,使用二分查找法,因为链表在未连接之前已排好序,找到之后插入;
操作2直接让其右端点等于下一个的左端点即可,在链表最后一位的必定撞墙
然后突然发现自己不会写链表qaq,凉了
于是打暴力qaq绝对不满分,还可能爆零的那种(\\\a\\\)
#include<iostream> #include<algorithm> using namespace std; const int n=500010; struct ball{ double l,r; ball *next; }b[n]; int n,q,p; int pp=0; bool cmp(ball b1,ball b2); void insertball(int l,int r,int x); void simulate(); int main() { cin>>n>>q>>p; for(int i=1;i<=n;i++) { cin>>b[i].l; b[i].r=b[i].l+1; } sort(b+1,b+1+n,cmp); for(int i=1;i<=q;i++) { int t; cin>>t; switch(t) { case 1: int x; cin>>x; pp++; b[n+pp].l=x; b[n+pp].r=x+1; sort(b+1,b+1+n+pp,cmp); break; case 2: simulate(); break; } } for(int i=1;i<=n+pp;i++) { cout<<b[i].l<<" "; } cout<<endl; return 0; } bool cmp(ball b1,ball b2) { return b1.r<b2.r; } void simulate() { for(int i=1;i<=n+pp-1;i++) { b[i].r=b[i+1].l; b[i].l=b[i].r-1; } b[n+pp].r=p; b[n+pp].l=p-1; }
等我找到了正解之后再扔上来qwq