题解：P10688 Buy Tickets

_o_sunshine_o_ · 2024-08-11 15:30:05 · 题解

题目大意

排队时有人插队。

输入格式

给定队列长度 n 。
接下来 n 行每行两个正整数，第一个表示该元素插入位置，另一个表示该元素的权值。

输出格式

按照顺序输出该位置元素的权值。

注意事项

• 输入的数据组数未知，需要一直输入，输入方法可以参考以下代码。

  while (cin>>n){
  //操作
  }

• 由样例可知，排队的位置从 0 开始。

  解析

  首先要解决这道题第一个问题便是关于插队的处理。
  这个人插入到队伍的 i 位置，那么 i 位置后的人的位置都要向后移 1 位。
  关于解决这个问题这里有两种方法：

  1. 上篇题解 @ fangminding 大佬的方法：使用 vector 容器中的 insert 函数，具体用法这里不过多赘述，感兴趣的可以去看他的题解。
  2. 本蒟蒻使用的朴素算法，具体解释在代码里：

void charu(int a,int b){
    int t=arr[a];//存储在 a 位置原来的元素权值 
    arr[a]=b;   //将其替换为现在插入的元素权值 
    for(int i=a+1;i<n;i++){//从第 a+1 位开始往后推移 
        int t1=arr[i];//存储第i位的元素权值 
        arr[i]=t; //将第 i 位改为上一位的元素权值 
        t=t1;//将 t 更新 
    }
}

怎么样，是不是很朴素？凸显蒟蒻之菜
解决了这个问题接下来就很简单了：
边插入我们边处理，如果该位置没有人，那肯定最好，直接插入就行，如果有人，那就是上面插队的情况了。
最后附上完整代码：

#include<iostream>
#include<cstring>
using namespace std;
int arr[200005];
int n;
void charu(int a,int b){
    int t=arr[a];//存储在 a 位置原来的元素权值 
    arr[a]=b;   //将其替换为现在插入的元素权值 
    for(int i=a+1;i<n;i++){//从第 a+1 位开始往后推移 
        int t1=arr[i];//存储第 i 位的元素权值 
        arr[i]=t; //将第 i 位改为上一位的元素权值 
        t=t1;//将t更新 
    }
}
int main(){
    while(cin>>n){
        memset(arr,0,sizeof arr);
        for(int i=1;i<=n;i++){
            int a,b;
            cin>>a>>b;
            if(arr[a]==0){//没有人 
                arr[a]=b;
            }else{  //插队 
                charu(a,b);
            }
        }
        for(int i=0;i<n;i++){
            cout<<arr[i]<<' ';
        }
        cout<<endl;//如果你第一个点 wa ，那么可能就是你这里没换行 
    }
    return 0;
}

最后，这是本蒟蒻的第一篇公开题解，审核辛苦了！望通过，若有错误，打下来一点整改！
蒟蒻也想弱弱的说一句：点个赞呗 qwq 。