有趣的问题

Published: by Creative Commons Licence

  • Tags:

文件命名问题

给定$n$个文件名,第$i$个文件名记作$name_i$,要求我们在文件系统中创建对应的$n$个文件。

文件系统的规则是这样的,如果我们要创建名字为$x$的文件,那么如果文件系统中已经存在同名文件了,我们就需要将新创建的文件名改成x(1),x(2),...中第一个未被使用的名字。

要求判断每个文件在创建后的文件名是啥。

题目地址

一个简单的做法,就是我们充当文件系统的角色,用哈希表维护所有出现的文件名,然后逐一去判断。下面给出代码:

String getName(String x, int index) {
  String y = x;
  if(index > 0) { 
    y += "(" + index + ")"
  }
  return fileSystem.contains(y) ? getName(x, index + 1) : y;
}

但是稍微思考一下就会发现,如果文件名都相同,那么时间复杂度会恶化到$O(n^2)$。

实际上上面的问题我们可以$O(n)$解决,做法就是为每个名字$x$,都维护一个计数器$C(x)$,表示目前已知$x$的最大编号,初始值为$-1$。

接下來,当我们处理文件名$x$的时候,如果$C(x)=-1$就尝试$x$,否则我们先尝试x(C(x)+1),如果文件系统存在了就尝试下一个。一直到找到第一个不存在的文件名$x(t)$。之后我们将$C(x)$更新为$t$。

下面我们证明上面算法的时间复杂度是$O(n)$。可以发现上面过程中可能会导致时间复杂度超过$O(n)$的部分就是上面的循环尝试x(C(x)+1),x(C(x)+2),...的部分,这时候已经确认$x$存在于文件系统了。

考虑x(C(x)+1)尝试失败的原因,这个文件只可能是因为我们首次创建了一个名字叫做x(C(x)+1)的文件。同时发现x(C(x)+1)这个文件的创建也只会使得x的循环部分增加1。

因此我们知道最终只会创建最多$n$个名字,因此上面循环试错阶段总长度也是$O(n)$的,总的时间复杂度就是$O(n)$。

归0问题

给定$n$个数$a_1,\ldots,a_n$,每个数的范围都在$-1000$到$1000$范围内。要求找到一组非负系数$c_1,\ldots,c_n$,满足$\sum_{i=1}^nc_ia_i=0$,且$\sum_i^nc_i$最小。其中$n\leq 10^6$。

一道题目

先讲一下我的做法。首先如果有解,要么存在某个$a_i=0$,要么存在两个数$a_i<0<a_j$。前者非常简单,所以我们仅讨论一下后者。这时候我们发现取$c_i$取$a_j$,而$c_j$取$-a_i$的时候,就有$c_ia_i+c_ja_j=0$。因此我们可以直接推出结果不可能超过$2000$。

实际上我们可以将$a$序列去重,这样就能保证$n\leq 2000+1$。

我们可以用最短路来解决这个问题,初始点为$a_1,\ldots,a_n$,而最短路需要考虑的范围为$-2\cdot 10^6$到$2\cdot 10^6$之间。把每个数当成边,边长都是$1$,因此如果我们用BFS的话时间复杂度为$O(8\cdot 10^9)$。但是这里可以用BitSet优化,因此时间复杂度为$O(\frac{8}{6}\cdot10^8)$。还是可以接受的。

但是这个问题实际上可以优化到$O(2001^2)$。我们可以认为取到的最短的总和为0的序列为$b_1,\ldots,b_k$,由于前缀和和后缀和异号,因此我们能通过调整顺序保证所有前缀和的绝对值都不超过$1000$。于是我们就只需要为$-1000$到$1000$建立$2001$个顶点,跑最短路。

并且这里我们还可以继续采用BitSet进行优化,这样时间复杂度可以降低到$O(\frac{2001^2}{60})$。

环上最小相邻元素差

**给定$n$个数$a_1,\ldots,a_n$。我们将其重新排列组合,组成一个环$b_1,\ldots,b_n$,其中$b_1$与$b_n$相邻。记这样的排列的费用为$\max_{i}|b_{i+1}-b_i $。找出一个排列使得费用最小。**

一道牛客的题目

对于$n\leq 2$的情况,这个问题是微不足道的。考虑$n>2$的情况。

我们先认为$a_1,\ldots,a_n$是递增的(如果不是,就先排个序)。之后我们考虑序列$a_1,a_3,a_5,\ldots,a_4,a_2$,即我们将下标为奇数的按原序排在前面,下标为偶数的按逆序排在后面。记$c$为这样排列的费用,我们证明$c$是最小的费用。

假设最优排列的费用$t$小于$c$,则我们可以找到一个下标$i$,满足$a_{i+2}-a_{i}=c$。我们将下标小于等于$i$的数记作第一类数,将$a_{i+1}$记作第二类数,将小标大于等于$i+2$的数记作第三类数。我们可以发现在最优排列中第一类数和第三类数是不允许相邻的。但是由于第一类数和第三类数都是存在的,且第二类数仅有一个。我们从环上删除唯一的第二类数,这时候环变成一个链表,此时第一类数和第三类数一定会相邻。

牛吃饲料问题

一条直线上,在位置0处有$n$条牛,第$i$条牛需要吃$a_i$单位草才能吃饱。现在有$m$个地方提供饲料,第$i$个地方的位置在坐标$x_i$。每个饲料点同时只能喂养一头牛,每头牛可以有如下每秒钟可以做如下操作:

  • 向左或向右移动1单位距离
  • 如果处于某个饲料点,则可以吃1单位饲料

问最少花多少时间,才能把所有牛喂饱。其中$1\leq a_i,x_i \leq 10^9,1\leq n,m\leq 10^5$。

这道题来源于SRM739的HungryCowsMedium。

一开始我的想法是错误的,我认为最优解情况下一头牛只可能在一个饲料点吃草,这时候问题变成有$m$个背包,$n$个物品,判断是否有一种方案可以将所有物品装入到背包中。在背包数目多于2的情况下,问题是无法求解的。

但是实际上牛可以在多个位置吃草。比如a=[4,4,4]x=[2,4]的情况下,答案是$9$。

我们可以发现如果答案是$t$,则位于$x_i$的饲料点能提供的饲料量为$\max(0, t-x_i)$。我们按照这些草料产生的时间从大到小编号,第一份的编号为$1$。我们可以通过预先对$x_i$进行排序,因此可以发现每个饲料点能提供的饲料量随着下标的增大而递减。

下面我们发现如果一头牛$k$如果在第$i,j$个饲料点都吃了草,且$i\lt j$,且记$l_k(i)$为牛$k$在第$i$个位置吃的第一份草的编号,则$r_k(i)$表示牛$k$在第$i$个位置吃的最后一份草的编号,可以发现$r_k(i)\lt l_k(j)$。

我们可以发现第$i$头牛只能吃前$L(i)$个位置的草料。这就给了我们一个贪心的思路,就是我们按牛的食量从大到小进行排序。而牛从第一个位置的草料开始吃,并优先吃编号较大的草料。

众数问题

题目1:给定$n$个数$a_1,a_2,\ldots,a_n$,以及整数$k$,要求找出其中任意一个出现超过$n/k$次的元素,如果有多个,任意输出其中一个,否则输出$-1$。

我们可以不断从集合中删除$k$个不同的元素,直到不同的元素数目少于$k$,如果一个数出现超过$n/k$次,则其最终一定会被剩下来。这个过程可以$O(kn)$完成。

之后对每个出现的元素,考虑它们的出现次数即可。时间复杂度为$O(kn)$,空间复杂度为$O(k)$。当然如果我们直接统计每个数出现的次数时间复杂度为$O(n)$,空间复杂度为$O(n)$。

题目2:给定$n$个数$a_1,a_2,\ldots,a_n$,记$f(k)$表示我们允许每次删除$k$个不同的元素,最多能执行多少次操作。要求输出$f(1),f(2),\ldots,f(n)$。

一道题目

我们先进行离散化,记$c_i$表示整数$i$出现的次数。对于给定的$k$,我们可以设计一个贪心算法,就是每次选择出现次数最多的$k$个数各删除一个。这个算法跑一轮的时间复杂度为$O(n\log_2n)$,总的时间复杂度为$O(n^2\log_2n)$。

我们发现如果一个数出现次数超过$n/k$,则我们每次都必定会选择它,换言之,问题实际上在问,在剩余的数中,我们每次可以选择$k-1$个不同的数删除,问最多执行多少次操作。

命题:对于任意$n\geq 0$,如果每个数的出现次数不超过$n/k$,那么总共可以执行操作$\lfloor \frac{n}{k} \rfloor$次。

证明:通过归纳法证明。当$n\lt k$的时候,因为每个数出现次数不超过$n/k$,即每个数出现次数都是$0$,因此答案是$0$。对于$n\geq k$,且$n-1$时命题成立,那么由于每个数出现次数都不超过$n/k$,因此出现次数最多的$k$个数,都至少出现了$1$次。我们将出现次数按从大到小排序,记做$b_1,b_2,\ldots,b_m$。我们选择最多的$k$个数执行一次操作后,接下来需要证明所有数次数不超过$(n-k)/k=n/k-1$。很显然对于$b_1-1,\ldots,b_k-1$是满足条件的,我们再考虑$b_{k+1}$。由两种情况,一种是$b_{k+1}\lt b_1$,这时候由于$b_{k+1}\leq b_1-1$,因此所有数都满足条件。还有一种情况是$b_{k+1}=b_1$,若$b_{k+1}>n/k-1\Rightarrow b_{k+1}\geq n/k$。则由于$b_1\geq b_2\geq \ldots \geq b_{k+1}$,即$\sum_{i=1}^{k+1}b_i\geq (n/k)\cdot (k+1)>n$,这是不可能的。因此我们证明了对于任意非负整数$n$,命题都成立。

模运算下的比较

题目1:给定一个序列$a_0,a_1,\ldots,a_{n-1}$,其中$a_i=y+ix\mod m$,$x$是给定的数,要求计算有多少个$j$,满足$j<n-1$且$a_{j}<a_{j+1}$。其中$1\leq n,m,x,y \leq 10^9$。

如果$x=0$,则答案为$0$。否则我们可以通过统计有多少项$j$,满足$a_{j}\geq a_{j+1}$来得到结果。由于$x\neq 0$,因此我们只需要考虑$a_j>a_{j+1}$的情况即可。

这个不是很好统计,但是如果我们能注意到此时一定有$\lfloor \frac{(j+1)x+y}{m} \rfloor=\lfloor \frac{jx+y}{m} \rfloor+1$,那么问题就迎刃而解了。

答案就是$\lfloor \frac{(n-1)x+y}{m} \rfloor$。