欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

上一篇: 课堂笔记10.22

下一篇: JNI-C