題目鏈接：http://118.190.20.162/view.page?gpid=T56

題目分析

• 一開(kāi)始看到題目描述以為是一道有點(diǎn)意思的算法題，看完數(shù)據(jù)范圍1 ≤ n ≤ 1000，1 ≤ m ≤ 1000，發(fā)現(xiàn)原來(lái)是普通的模擬題。
• 需要用到一個(gè)mark數(shù)組記錄各個(gè)編號(hào)學(xué)生所在的位置，每次調(diào)整隊(duì)列時(shí)，先通過(guò)mark數(shù)組得到第p號(hào)學(xué)生的位置，然后根據(jù)q的正負(fù)值對(duì)p號(hào)學(xué)生的位置進(jìn)行調(diào)整，調(diào)整的過(guò)程中要記得更新mark數(shù)組的值。雖然做下來(lái)是$O(mq)$的時(shí)間復(fù)雜度，但是跑得挺快的hhh。

代碼如下

#include <iostream> #include <algorithm> using namespace std; const int maxn = 1005; int n, m, p, q; //a[i]表示i號(hào)位置站的學(xué)生編號(hào)，mark[i]表示i號(hào)學(xué)生的位置 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; }

總結(jié)

以上是生活随笔為你收集整理的ccf-csp #201703-2 学生排队的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。