娱乐 每 日 算 法 挑 战 （大嘘）【第0x18期】

[Mr.K 018]

第24期终于来了……

快到期末了，下一期啥时候能出还是个未知数……

嘛，好歹这一期出来了不是么？

今天这道题其实是个操作系统题，题本身不太难。

第24期 我的世界2

K上一次在MC里搭了个奇观（雕塑）之后，这次又想再搭一个奇观。这次他要搭一个像素画。他这个人其实没什么美术细胞，所以搭像素画的方式跟别人不太一样：首先写了个程序，用一些（可以再水出一期算法挑战的）技术手段导出了一张表格，告诉他每一格该搭什么方块。之后，把要搭的图像输入进去，拿到表格，对着表格搭像素画。

K按照表格搭像素画的时候，发现他的快捷栏不够大，只能容纳9个方块，因此下一个要搭的方块常常没有出现在快捷栏里面。这时只能去方块表里找，找到对应的方块之后再放在快捷栏里的某个位置（那个位置里如果原先有方块，就被换掉了）。众所周知从方块表里找一个特定方块是非常麻烦的，因此K打算尽可能减少从方块表里找方块的数量。

现在告诉你像素画某一行的各个方块分别是什么，快捷栏初始时是空的。试问K最少需要从方块表里找多少次方块？

输入

第一行两个整数m n，m表示有多少种方块，n表示要处理的方块数量，即像素画这一行的长度。满足0<m<1000, 0<n<100 000。 （不要问为什么要摆那么多方块，问就是盖奇观）

接下来n行，每行一个整数a_n，表示这个位置的方块种类，满足0<=a_n<m。

输出

一个整数，表示找方块的最少次数。

以上。另外还有一道附加题，和上次一样，不保证存在多项式时间的解这个题根本就是不存在了吧（。

要从家里出去去若干个地方买东西。不妨认为家在(0,0)处，其余的商店都在平面上的某个位置。由于街巷和建筑物的限制，在两个点之间移动只能横平竖直地移动。出发时携带了质量为1单位的物品，每个商店都有一个质量值，表示到那个商店后身上另外携带的质量。从家里出发，要访问所有的商店后再回家。定义每段路的体力花费为路程和携带质量的乘积。

试求一个访问商店的序列，按这个顺序访问商店，总的体力花费最小。

--------------1705更新--------------

经 @yhz012 的提醒，基本确定这个附加题是个NP完全问题

五月 18, 2020，由Mr.K 018修改

[yhz012]

艹基础题是缓存命中问题

 

附加题……曼哈顿距离，边的权重可变，求traveling sales man……

我觉得这已经不是不保证了吧，完全可以规约到普通的TSP问题，只要令所有商店的物品重量为0即可……

五月 18, 2020，由yhz012修改

[Mr.K 018]

57 分钟前, yhz012 说道:

艹基础题是缓存命中问题

 

附加题……曼哈顿距离，边的权重可变，求traveling sales man……

我觉得这已经不是不保证了吧，完全可以规约到普通的TSP问题，只要令所有商店的物品重量为0即可……

附加题是我真的想在生活中这么优化一下，所以并没有考虑复杂度（

那这么看，恐怕只能分支限界一下

[yhz012]

11 分钟前, Mr.K 018 说道:

附加题是我真的想在生活中这么优化一下，所以并没有考虑复杂度（

那这么看，恐怕只能分支限界一下

我觉得这问题本身确实很有意思，而且直球来说其实我最近在做和这边有关的算法

感觉有一些能挣扎的地方，但是我的大脑现在处于罢工状态……

[Mr.K 018]

7 分钟前, yhz012 说道:

我觉得这问题本身确实很有意思，而且直球来说其实我最近在做和这边有关的算法

感觉有一些能挣扎的地方，但是我的大脑现在处于罢工状态……

我在想，修改题目中的条件，改成不必只有最后才能回家，而是随时可以回家放东西，出来后身上的重量值回到1，这个题是变得简单了还是更复杂了

[yhz012]

11 小时前, Mr.K 018 说道:

我在想，修改题目中的条件，改成不必只有最后才能回家，而是随时可以回家放东西，出来后身上的重量值回到1，这个题是变得简单了还是更复杂了

我直觉是这俩问题难度一样？但是我还没想好怎么构造问题来互相归约

 

如果一样，那某种意义上我们可以用最小生成树来求bounded approximate solution。

 

在想如果我允许vertex的weight是负的，但是agent的weight始终是max(1, tempW)，是不是在原点处增加n个负w顶点就可以归约了……

我需要证明回家一定只会吃掉手上相同的权重的负w顶点……多吃肯定是亏的，主要问题是少吃的情况……

五月 18, 2020，由yhz012修改

[清夏sama]

不玩mc 这个搭像素画是必须按着顺序搭么 0.0

[Mr.K 018]

2 分钟前, 清夏sama 说道:

不玩mc 这个搭像素画是必须按着顺序搭么 0.0

其实原则上不是，这里是为了出题做的简化

而且实际上不按顺序搭会带来其他问题……我这个K后来觉得还是一个个搭好一点

[Mr.K 018]

没人来看啊……感觉这个题应该没那么难了吧？

[yhz012]

于 2020/5/18 于 AM10点05分, Mr.K 018 说道:

没人来看啊……感觉这个题应该没那么难了吧？

说实话我操作系统没学好，题目里要求最少，我需要对全局优化么，比如假设全局是

123456789

000000000

111111111

222222222

……

999999999

那么显然我要是使用最后一次使用离现在最远的策略，毫无疑问我的找方块数的次数要增加，但是这个前提是我预先已经知道了第三行我要用1

换句话说，输入的数据我是否应当视作流数据，每次我只读一行，还是我预先先读取所有行（甚至某种程度上搭方块也可以不按照行的顺序）？

[Mr.K 018]

4 小时前, yhz012 说道:

说实话我操作系统没学好，题目里要求最少，我需要对全局优化么，比如假设全局是

123456789

000000000

111111111

222222222

……

999999999

那么显然我要是使用最后一次使用离现在最远的策略，毫无疑问我的找方块数的次数要增加，但是这个前提是我预先已经知道了第三行我要用1

换句话说，输入的数据我是否应当视作流数据，每次我只读一行，还是我预先先读取所有行（甚至某种程度上搭方块也可以不按照行的顺序）？

输入数据只包含一行，这是因为多行可以轻易地当成一行处理。

这个实际上是对应OPT调度算法。操作系统里之所以用LRU之类的算法是因为难以确定之后使用“方块”（可以理解为cache行，内存页甚至磁盘块啥的都行）的情况，只能用既往的情况去推将来。但本题里用方块的情况是完整地告诉程序的，这个规模的输入数据全存下来也不会MLE，所以用OPT即可。

姑且做得仿真一点，我们认为搭方块还是要按顺序的，因为实际操作中不按顺序搭方块真的会增大记忆开销的（因为会涉及到寻址的问题），而且允许不按顺序搭方块的话这题不就退化成数输入中有多少个不同的数了吗kora

[yhz012]

48 分钟前, Mr.K 018 说道:

这题不就退化成数输入中有多少个不同的数了吗kora

好像是这么回事（装傻

所以总结来说就是我事先是可以读取所有要用方块的，然后按序摆方块就好了对吧

 

那我最暴力的写法就是开一个m长数组next，初始化为inf，然后倒序遍历整个像素画，更新记录之后在第几个方块使用，接着正序更新最不迫切需要的方块就好了吧

next = [[float('inf')] for i in range(m)] #初始化全inf

index = n
for block in reversed(blockList): #倒序遍历
  index = index - 1
  next[block].insert(index, 0) #记录下次使用index

hand = np.full(9, np.inf) #初始化手里的方块
handSize = hand.size #记录手里的空间
count = 0 #记录查找次数
for block in blockList:
  if block not in hand: #不在手里
    if handSize > 0: #手里有空间
      hand[handSize] = block #拿到手里
      count = count + 1
      handSize = handSize - 1
    else: #没空间
      index = argmax(next[hand]) #手里面的方块中，next最大的
      hand[index] = block #替换方块
      count = count + 1

  next[block].pop(0) #拿在手里后，定位下一个方块位置
return count

 

五月 20, 2020，由yhz012修改