ccf-csp #201703-2 学生排队

题目链接：http://118.190.20.162/view.page?gpid=T56

题目分析

• 一开始看到题目描述以为是一道有点意思的算法题，看完数据范围1 ≤ n ≤ 1000，1 ≤ m ≤ 1000，发现原来是普通的模拟题。
• 需要用到一个mark数组记录各个编号学生所在的位置，每次调整队列时，先通过mark数组得到第p号学生的位置，然后根据q的正负值对p号学生的位置进行调整，调整的过程中要记得更新mark数组的值。虽然做下来是$O(mq)$O(mq)的时间复杂度，但是跑得挺快的hhh。

代码如下

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1005;
int n, m, p, q;
//a[i]表示i号位置站的学生编号，mark[i]表示i号学生的位置
int a[maxn], mark[maxn];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		a[i] = i;
		mark[i] = i;	
	}
	for (int i = 1; i <= m; i++) {
		cin >> p >> q;
		int idx = mark[p];
		if (q > 0) {
			for (int i = 0; i< q; i++) {
				mark[a[idx + i]]++;
				mark[a[idx + i + 1]]--;
				swap(a[idx + i], a[idx + i+ 1]);
			}
		} else {
			q = -q;
			for (int i = 0; i< q; i++) {
				mark[a[idx - i]]--;
				mark[a[idx - i - 1]]++;
				swap(a[idx - i], a[idx - i - 1]);
			}
		}
		
	}
	for (int i = 1; i <=n; i++) {
		cout << a[i] << " ";
	}
	cout << endl;
	return 0;
}