本页面已浏览96次

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要移动,因为在原始排列中,2a[3]=3后面(右边),而目标排列中,23前面(左边)。

所以,结论是: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=1b的5=2 => a的5=2……
  4. 现在的a数组:[2 4 5 3 1]

问题约简为:找到a中数字的位置靠右但数字本身应该在前的那些数字(以上面第4步中得到的数组看,是31这两个数字,因此需要调整两次: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可以拼写COWZOOMOVE。令人难过地,她无法拼出MOO,因为唯一包含M的积木不能同时用于O。她无法拼出FARM,因为没有包含字母R的积木。她无法拼出CODE,因为CDE属于同一块积木。

分析

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

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

答案

思考

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

Previous Post Next Post