本页面已浏览69次

1. Sleeping in Class

奶牛Bessie很兴奋最近重返线下上课了！不幸的是，她的讲师Farmer John讲课非常无聊，因此她经常在课堂上打瞌睡。

Farmer John注意到Bessie在课堂上没有专心听讲。他让班上的另一名学生Elsie记录Bessie在一节课中睡着的次数。总共有N个课时（\(1\le N\le 10^5\)），Elsie记录下Bessie在第i个课时睡着了\(a_i\)次（\(0\le a_i\le 10^6\)）。Bessie在所有课时期间睡着的总次数不超过\(10^6\)。

Elsie感觉与Bessie竞争非常激烈，从而想让Farmer John觉得Bessie在每节课上总是睡着相同的次数——让问题看起来完全是Bessie的错，而与Farmer John有时无聊的讲课无关。Elsie可以修改记录的唯一方式是合并两个相邻的课时。例如，如果\(a=[1,2,3,4,5]\)，那么如果Elsie合并第二和第三课时则记录将变为\([1,5,4,5]\)。

帮助Elsie计算她需要对记录进行的最小修改次数，使得她可以令记录中的所有数相等。

输入格式（从终端 / 标准输入读入）：

每个测试用例包含T（$1\le T\le 10）个需要独立求解的子测试用例。

输入的第一行包含T，为需要求解的子测试用例的数量。以下是T个子测试用例，每个子测试用例包含两行。第一行包含N，第二行包含\(a_1, a_2, ..., a_N\)。

输入保证在每个子测试用例中，a中所有数之和不超过\(10^6\)。同时输入保证所有子测试用例的N之和不超过\(10^5\)。

输出格式（输出至终端 / 标准输出）：

输出T行，对每个子测试用例输出Elsie可以令记录中的所有数相等所需进行的最小修改次数。

输入样例：

3
6
1 2 3 1 1 1
3
2 2 3
5
0 0 0 0 0

输出样例：

3
2
0

对于第一个子测试用例，Elsie 可以通过 3 次修改将使得她的记录中仅包含3。

1 2 3 1 1 1
-> 3 3 1 1 1
-> 3 3 2 1
-> 3 3 3

对于第二个子测试用例，Elsie 可以通过 2 次修改将她的记录变为7。

2 2 3
-> 2 5
-> 7

对于最后一个子测试用例，Elsie无需执行任何操作；记录已经由相等的数组成。

分析

本题的关键点在于，不管怎么调整，总和\(sum(a)=a_1+a_2+...+a_N\)是不变的。所以，我们不妨这样思考：

不管做多少次调整，最后剩下了r组，而且这些组中数字和都相同，这些组中的数字和肯定是\(\frac{sum}{r}\)（整数）。以1 2 3 1 1 1为例，\(r=3\)，而\(\frac{sum}{r}=3\)，也就是：分组为[1 2] [3] [1 1 1]。当然，r越大，需要的操作就越少。

对于每个r，我们可以从左到右遍历数组，并确定是要再加一个元素呢，还是开一个新的元素。

最终，需要调整的次数是元素的个数（N）减去最后的分组（r）。

答案

思考

这道题的复杂度是？从代码来看，很可能是一个双重循环。16行有一个循环（\(1 - N\)）。

for (int r = n; r >= 1; r--)

23行也有一个循环

for (int i = 0; i < n; i++)

很容易让我们得出时间复杂度是\(O(N^2)\)的结论。但是，注意到18行有一个判定，也就是判定r是不是n的因子。对于\(N\le 10^6\)的整数，它的因子数不超过240。所以严格说，本题的时间复杂度为\(O(N*睡觉时间总和的因子数)\)。

所以，这段代码运行不会超时。

2. Photoshoot 2

这是一个似乎很熟悉的情况，Farmer John正在将他的N头编号为\(1 ... N\)的奶牛（\(1\le N\le 10^5\)）排成一排，以便拍照。

最初，奶牛从左到右按\(a_1, a_2, ... , a_N\)的顺序排列。Farmer John的目标是将奶牛从左到右按\(b_1, b_2, ..., b_N\)的顺序排列。为此，他可以对排序进行一系列修改操作。每次修改操作可以选择一头奶牛并将其向左移动一些位置。

请计算 Farmer John将奶牛排列成所要求的顺序所需的最小修改次数。

输入格式（从终端 / 标准输入读入）：

输入的第一行包含N。第二行包含\(a_1, a_2, ..., a_N\)。第三行包含\(b_1, b_2, ..., b_N\)。

输出格式（输出至终端 / 标准输出）：

输出将奶牛排列成所要求的顺序所需的最小修改次数。

输入样例：

5
1 2 3 4 5
1 2 3 4 5

输出样例：

0

在这个例子中，奶牛已经排列成所要求的顺序，所以无需进行修改操作。

输入样例：

5
5 1 3 2 4
4 5 2 1 3

输出样例：

2

在这个例子中，两次修改操作足够了。以下是一种Farmer John重新排列他的奶牛们的方式：

选择奶牛 4
 并将其向左移动四个位置。
选择奶牛 2
 并将其向左移动两个位置。
   5 1 3 2 4
-> 4 5 1 3 2
-> 4 5 2 1 3

分析

先观察一下“移动”发生在什么情况下：

以5 1 3 2 4 => 4 5 2 1 3为例，一眼看出，a[4]=2要移动，因为在原始排列中，2在a[3]=3后面（右边），而目标排列中，2在3前面（左边）。

所以，结论是：a中的某个\(a_i\)在\(a_j\)左边，但在b中，\(a_i\)在\(a_j\)右边，那么\(a_j\)必须要移动。

    for (int i = 0; i < N; ++i)
    {
        for (int j = i + 1; j < N; ++j)
        {
            if (pos_in_B(A[i], B) > pos_in_B(A[j], B))
            {
                need_to_move[j] = 1;
            }
        }
    }

这是一个\(O(N^3)\)的过程。因为本身是两个循环，同时判定位置又要进行一次\(O(N)\)的扫描。

有没有办法优化呢？当然可以！上述的过程中，我们要进行两个循环，是因为两个“排列顺序”都是没有排过序的。因此，我们不得不将所有可能的排序对(i, j)都排列出来。如果我们认为b就是一种排列好的顺序，a是为排列前的顺序，问题归并为一般情况下的排序过程的复杂度，也就是\(O(N^2)\)。

当然我们要做一个映射，“目标”顺序用1, 2, 3, ..., N来表示，而原始顺序中的“数字”要用目标中的新数字来表示。如下：

1. 原来的b数组：[4 5 2 1 3] => [1 2 3 4 5]
2. 原来的a数组：[5 1 3 2 4]
3. 映射规则：b的4=1 => a的4=1，b的5=2 => a的5=2……
4. 现在的a数组：[2 4 5 3 1]

问题约简为：找到a中数字的位置靠右但数字本身应该在前的那些数字（以上面第4步中得到的数组看，是3和1这两个数字，因此需要调整两次：1左移四次，2左移两次。

翻成数学语言就是：对于每个j，找到\(i\lt j\)同时\(a_i>a_j\)的数量。这就是一个\(O(N^2)\)的过程。

核心代码如下：

    for (int i = 0; i < N; ++i)
    {
        pos_in_B[B[i]] = i + 1;
    }

    for (int i = 0; i < N; ++i)
    {
        A[i] = pos_in_B[A[i]];
    }

    int ans = 0;
    for (int j = 0; j < N; ++j)
    {
        bool need_to_move_j = false;
        for (int i = 0; i < j; ++i)
        {
            if (A[i] > A[j])
            {
                need_to_move_j = true;
                break;
            }
        }
        if (need_to_move_j)
        {
            ans += 1;
        }
    }

这是一个很纯粹的\(O(N^2)\)复杂度，可以将它类比于某种常规排序算法。当然，我们这里不进行排序的动作，而只计算“排序”的次数。

答案

思考

还能不能优化呢，比如到\(O(N)\)？

考虑到我们给出的答案的思路：只找要“排序”的次数而并不关心最终的排序结果。

我们看下经过映射后的a数组：[2 4 5 3 1]。

1. 2先不动。目前我们看到的目前最大数是2。
2. 看4，它比目前最大数大，符合最终排序的顺序。不动。目前最大数是4。
3. 看5，它比目前最大数大，符合最终排序的顺序。不动。目前最大数是5。
4. 看3，它比目前最大数小，要动。目前最大数是5。
5. 看1，它比目前最大数小，要动。目前最大数是5。

我们的思路变成：然目标排列是排好且升序的（基于当前的代码），我们不妨从左到右开始，跟踪当前的最大值是多少？

如果当前值（a[j]）大于（一直到j-1为止的）当前最大值，那么没问题，这个数字位置不用动，更新当前最大值即可；否则，这个数字就是失位的，要被调整。

这么做我们只要扫描一次即可，时间复杂度削减为\(O(N)\)。

完整代码就不给出了。请大家基于上面给出的代码加以改写。

3. Blocks

为了提高她的词汇量，奶牛Bessie拿来了一套共四块积木，每块积木都是一个正方体，六面各写着一个字母。她正在将积木排成一排，使积木顶部的字母拼出单词，以此来学习拼写。

给定Bessie四块积木上的字母，以及她想要拼写的单词列表，请判断她可以使用积木成功拼写列表中的哪些单词。

输入格式（从终端 / 标准输入读入）：

输入的第一行包含N（\(1\le N\le 10\)），为Bessie想要拼写的单词数。以下四行，每行包含一个包含六个大写字母的字符串，表示Bessie的一块积木六面上的字母。以下N行包含Bessie想要拼写的N个单词。每一个均由1到4个大写字母组成。

输出格式（输出至终端 / 标准输出）：

对于Bessie的列表中的每一个单词，如果她可以拼写这个单词则输出YES，否则输出NO。

输入样例：

6
MOOOOO
OOOOOO
ABCDEF
UVWXYZ
COW
MOO
ZOO
MOVE
CODE
FARM

输出样例：

YES
NO
YES
YES
NO
NO

在这个例子中，Bessie可以拼写COW，ZOO和MOVE。令人难过地，她无法拼出MOO，因为唯一包含M的积木不能同时用于O。她无法拼出FARM，因为没有包含字母R的积木。她无法拼出CODE，因为C，D和E属于同一块积木。

分析

考虑一下用到四个积木的话：每个积木有6个字母，所以有\(6^4=1296\)种组合，乘以\(4!=24\)种不同的排列方式，所以一共有31104种不同的排列。用到3/2/1个积木的时候，排列数量只会更少。所以总共要测试的情形不会太多，可以用暴力法。

我们可以先将这些可能性算出来——当然可能有重复——存在一个集合中，然后根据输入的单词去找就是了。当然也可以输入一个单词后，每次都排列一次，因为数据量很小，也不会有问题——答案用的是这个思路。

答案

思考

请用另外一种方式（先储存所有可能的排列）解决这个问题。