有趣的问题

Published: June 22, 2020 by Daltao

• Categories:
• algorithm 101

• 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)$。

环上最小相邻元素差

给定$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\pmod 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$。