有趣的问题

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

最小斜率绝对值问题

给定$n$个二维平米的点$(x_1,y_1),\ldots,(x_n,y_n)$,其中每个点的横坐标值都不同。现在要求找到这样的$i,j$,满足$i<j$且$f(i,j)=\frac{|y_i-y_j|}{|x_i-x_j|}$最小。

这个问题是SRM787的一道题目。

做法非常简单。我们将所有点按照纵坐标值进行分组,如果某个组包含多个点,答案就一定是$0$。否则所有组都只有一个点。假设存在三个点$(x_a,y_a),(x_b,y_b),(x_c,y_c)$,满足$y_a<y_b<y_c$,那么可以发现$f(a,c)\geq \min(f(a,b),f(b,c))$(可以画图自己理解一下)。因此我们只需要将所有点按照高度排序,最小斜率绝对值一定可以通过排序后相邻两个点取到。

时间复杂度为$O(n\log_2n)$。

归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$的数记作第三类数。我们可以发现在最优排列中第一类数和第三类数是不允许相邻的。但是由于第一类数和第三类数都是存在的,且第二类数仅有一个。我们从环上删除唯一的第二类数,这时候环变成一个链表,此时第一类数和第三类数一定会相邻。