NOIP模拟赛D2T1自己的解题思路

来源：cnblogs　　作者：Scatter　　时间：2018/10/21 20:27:07　　对本文有异议

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;
}