题解：P12794 [NERC 2022] Easy Assembly

timshel · 2025-06-16 12:58:18 · 题解

整体思路

没啥难度，且时间和空间都很足，可以直接模拟。模拟题分步骤解决。

1. 把所有积木用向量排序并且排名。这里 vector 的排序需注意。

sort(val.begin(), val.end());

2. 统计连续数对。这里可以使用 map 来存储数字与其排序位置的关系，方便便利时调用。

3. 计算操作次数。我们可以通过画图找规律以及代值法发现公式。

   分裂次数 = 总积木数 - 初始塔数 - 有效连续对数

   合并次数 = 总积木数 - 1 - 有效连续对数

这样就结束了。这里附满分代码，代码中有注解。

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

int n;                          // 塔的数量
map<int, int> rmap;             // 数字到其排序位置的映射（用于快速查找数字的顺序）
vector<vector<int>> ts;         // 存储所有塔的积木数字（按从上到下顺序）
vector<int> val;                // 存储所有积木上的数字

int main()
{
    cin >> n;                   

    for (int i = 0; i < n; i++)
    {
        int k;
        cin >> k;                // 读取当前塔的积木数量
        vector<int> t(k);        // 创建存储当前塔积木的容器
        for (int j = 0; j < k; j++)
        {
            cin >> t[j];         // 读取当前塔的每个积木数字（从上到下顺序）
            val.push_back(t[j]); // 将数字存入全局数字列表
        }
        ts.push_back(t);         // 将当前塔存入塔列表
    }

    sort(val.begin(), val.end()); // 对所有积木数字进行排序，得到从小到大的顺序

    int m = val.size();           // 总积木数量
    // 建立数字到其排序位置的映射（排序后第1小的数字映射为1，第2小的映射为2，依此类推）
    for (int i = 0; i < m; i++)
    {
        rmap[val[i]] = i + 1;
    }

    int x = 0;                    // 记录各塔中满足"相邻数字在目标序列中也相邻"的对数
    for (int i = 0; i < n; i++)
    {
        int k = ts[i].size();     // 当前塔的积木数量
        // 检查塔中每对相邻积木
        for (int j = 0; j < k - 1; j++)
        {
            int a = ts[i][j];     // 当前积木数字（上方）
            int b = ts[i][j + 1]; // 下方积木数字
            int ra = rmap[a];     // 上方积木在目标序列中的位置
            int rb = rmap[b];     // 下方积木在目标序列中的位置
            // 如果下方积木在目标序列中是上方积木的下一个（即形成连续递增对）
            if (ra + 1 == rb)
            {
                x++;              // 记录这对有效连续对
            }
        }
    }

    // 计算最少操作次数
    // 分裂次数 = 总积木数 - 初始塔数 - 有效连续对数
    int s = m - n - x;
    // 合并次数 = 总积木数 - 1 - 有效连续对数（目标是将所有积木合并成1塔，需要m-1次合并，但连续对可减少合并次数）
    int c = m - 1 - x;
    cout << s << " " << c << endl;

    return 0;
}