本页面已浏览96次
奶牛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*睡觉时间总和的因子数)\)。
所以,这段代码运行不会超时。
这是一个似乎很熟悉的情况,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
来表示,而原始顺序中的“数字”要用目标中的新数字来表示。如下:
b
数组:[4 5 2 1 3]
=> [1 2 3 4 5]
a
数组:[5 1 3 2 4]
b的4=1
=> a的4=1
,b的5=2
=> a的5=2
……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]
。
2
先不动。目前我们看到的目前最大数是2
。4
,它比目前最大数大,符合最终排序的顺序。不动。目前最大数是4
。5
,它比目前最大数大,符合最终排序的顺序。不动。目前最大数是5
。3
,它比目前最大数小,要动。目前最大数是5
。1
,它比目前最大数小,要动。目前最大数是5
。我们的思路变成:然目标排列是排好且升序的(基于当前的代码),我们不妨从左到右开始,跟踪当前的最大值是多少?
如果当前值(a[j]
)大于(一直到j-1
为止的)当前最大值,那么没问题,这个数字位置不用动,更新当前最大值即可;否则,这个数字就是失位的,要被调整。
这么做我们只要扫描一次即可,时间复杂度削减为\(O(N)\)。
完整代码就不给出了。请大家基于上面给出的代码加以改写。
为了提高她的词汇量,奶牛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个积木的时候,排列数量只会更少。所以总共要测试的情形不会太多,可以用暴力法。
我们可以先将这些可能性算出来——当然可能有重复——存在一个集合中,然后根据输入的单词去找就是了。当然也可以输入一个单词后,每次都排列一次,因为数据量很小,也不会有问题——答案用的是这个思路。
请用另外一种方式(先储存所有可能的排列)解决这个问题。