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

[yhz012]

艹基础题是缓存命中问题

 

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

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

五月 18, 2020，由yhz012修改

[yhz012]

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

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

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

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

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

[yhz012]

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

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

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

 

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

 

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

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

五月 18, 2020，由yhz012修改

[yhz012]

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

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

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

123456789

000000000

111111111

222222222

……

999999999

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

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

[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修改