Luobuyu's Blog

0%

2826. 将三个组排序

发表于 分类于 ， ， 热度： ℃ 评论：
本文字数： 2.2k 阅读时长 ≈ 2 分钟
可以转化为最长上升子序列，或者前缀和，或者直接状态机。

2826.将三个组排序

题目描述：

给你一个下标从 0 开始长度为 n 的整数数组 nums 。

从 0 到 n - 1 的数字被分为编号从 1 到 3 的三个组，数字 i 属于组 nums[i] 。注意，有的组可能是 空的 。

你可以执行以下操作任意次：

  • 选择数字 x 并改变它的组。更正式的，你可以将 nums[x] 改为数字 1 到 3 中的任意一个。

你将按照以下过程构建一个新的数组 res ：

  1. 将每个组中的数字分别排序。
  2. 将组 1 ，2 和 3 中的元素 依次 连接以得到 res 。

如果得到的 res 是 非递减顺序的，那么我们称数组 nums 是 美丽数组 。

请你返回将 nums 变为 美丽数组 需要的最少步数。

数据范围：

$1\le nums.len \le 100;1\le nums[i] \le 3$

题解：

数组中的数全是 $1,2,3$ ，最后需要把数组变成 $11111,2222,3333$ 单调增的样式。可以先求一下最长上升子序列，然后直接用 $n - len(LIS)$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const int INF = 0x3f3f3f3f;

    int minimumOperations(vector<int> &nums)
    {
        int n = nums.size();
        vector<int> dp(n);
        for(int i = 0; i < n; ++i) dp[i] = 1;
        int ans = 0;
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < i; ++j)
            {
                if (nums[j] <= nums[i])
                {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            ans = max(ans, dp[i]);
        }
        return n - ans;
    }
};

使用优化的LIS算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const int INF = 0x3f3f3f3f;

    int minimumOperations(vector<int> &nums)
    {
        int n = nums.size();
        vector<int> dp(n + 1); // 长度为 i 的，末尾元素的值，单调增，可以二分
        int len = 1;
        dp[1] = nums[0];
        for (int i = 1; i < n; ++i)
        {
            if (nums[i] >= dp[len])
                dp[++len] = nums[i];
            else
            {
                // nums[i] < dp[len]
                // 找到第一个比nums[i]大的。修改为 nums[i]。首先 dp[len] 肯定满足
                // 可以在 [1, len) upper_bound 找，如果找不到返回的刚好是 len.
                int index = upper_bound(dp.begin() + 1, dp.begin() + len, nums[i]) - dp.begin();
                dp[index] = nums[i];
            }
        }
        return n - len;
    }
};

也可以使用状态机方法。状态只有结尾为 $1,2,3$ 三种状态。

$dp[i][1/2/3]$ 表示这三种状态，表示 $nums[i]$ 修改为 $j$ 并且满足递增的最小修改次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const int INF = 0x3f3f3f3f;
    int minimumOperations(vector<int> &nums)
    {
        int n = nums.size();
        vector<vector<int>> dp(n + 1, vector<int>(4));
        for (int i = 1; i <= n; ++i)
        {
            dp[i][1] = dp[i - 1][1] + (nums[i - 1] != 1);
            dp[i][2] = min(dp[i - 1][1], dp[i - 1][2]) + (nums[i - 1] != 2);
            dp[i][3] = min(dp[i - 1][1], min(dp[i-1][2], dp[i-1][3])) + (nums[i - 1] != 3);
        }
        return min(dp[n][1], min(dp[n][2], dp[n][3]));
    }
};