题解 P1188 【PASTE】

fanhy · 2019-02-20 18:14:30 · 题解

谁说O(N*K)算法要靠RP的

这题模拟才不到300ms，稳稳的

将一段文本剪切下来粘到另一段文本后面，相当于将这两段文本交换

使用temp数组记录下剪切下的文本，将另一段文本向前（插入行在原文本第一行之后）或向后（插入行在原文本第一行之前）。

将temp数组里的数赋值到该黏贴的位置就可以了。

AC代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100000 + 5;
int n, k;
int doc[MAXN], temp[MAXN];
int cnt;

int main()
{
    for (int i = 1; i < MAXN; i++) doc[i] = i;
    cin >> n >> k;
    for (int oper = 0; oper < k; oper++)
    {
        int s, t, p1, p2, ins, len;
        cin >> s >> t >> ins;
        len = t - s + 1;
        p1 = ins + 1;
        p2 = p1 + len - 1;
        cnt = 0;
        for (int i = s; i <= t; i++) temp[++cnt] = doc[i];
        if (ins < s) for (int i = s - 1; i >= p1; i--) doc[i + len] = doc[i];
        else for (int i = t + 1; i <= p2; i++) doc[i - len] = doc[i];
        for (int i = p2; i >= p1; i--) doc[i] = temp[cnt--];
    }
    for (int i = 1; i <= 10; i++) cout << doc[i] << endl;
    return 0;
}