堆积木

Enterprise_

发布于 2019-02-21 17:21:51

58400

代码可运行

运行总次数：0

代码可运行

题目描述 蒜头君有 n 块积木，编号分别为 1 到 n。一开始，蒜头把第 i 块积木放在位置 i。蒜头君进行 m 次操作，每次操作，蒜头把位置 b 上的积木整体移动到位置 a 上面。比如 1 位置的积木是 1，2 位置的积木是 2，那么把位置 2 的积木移动到位置 1 后，位置 1 上的积木从下到上依次为 1,2。

输入格式

第一行输入 2 个整数 n,m(1≤n≤10000,0≤m≤10000)。

接下来 m 行，每行输入 2 个整数 a,b(1≤a,b≤n)，如果a，b 相等则本次不需要移动。

输出格式

输出 n 行，第 i 行输出位置 i 从下到上的积木编号，如果该行没有积木输出一行空行。

样例输入1

2 2 1 2 1 2 样例输出1

1 2 样例输入2

4 4 3 1 4 3 2 4 2 2 样例输出2

2 4 3 1

题目分析： RT，移动积木，然后按行输出。
注意：内存超限，需要在每次移动完之后进行vector的强制内存释放，以及每次的空行输出。应该记录下每一层vector的长度，而不是每次都进行vec[i].size()的计算。
完整代码

#include<iostream>
#include<vector>
#include<cstdio>
using namespace std;
vector <int>vec[10005];
int main(void)
{
    int n, m, a, b, i, j, temp, tmp;
    scanf("%d%d", &n, &m);
    j = 0;
    for (i = 0; i < n; i++)
        vec[i].push_back(i + 1);
    while (m-- > 0)
    {
        scanf("%d%d", &a, &b);
        if (a == b)
            continue;
        if (!vec[b - 1].size())
            continue;
        tmp = vec[b - 1].size();
        for (j = 0; j < tmp; j++)
        {
            temp = vec[b - 1][j];
            vec[a - 1].push_back(temp);
        }
        vector<int>tt;
        vec[b - 1].swap(tt);
    }
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < vec[i].size(); j++)
        {
            if (!vec[i].size())
            {
                printf("\n");
                continue;
            }
            if (j == 0)
                printf("%d", vec[i][j]);
            else
                printf(" %d", vec[i][j]);
        }
        printf("\n");
    }
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2017年10月01日，如有侵权请联系 cloudcommunity@tencent.com 删除

size