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

ccf-csp #201703-2 学生排队

程序员文章站 2023-12-21 20:13:04
...

题目链接:http://118.190.20.162/view.page?gpid=T56
ccf-csp #201703-2 学生排队

题目分析

  • 一开始看到题目描述以为是一道有点意思的算法题,看完数据范围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;
}
相关标签: CSP认证

上一篇:

下一篇: