娱乐 每 日 算 法 挑 战 【第1期】

[yhz012]

艹，越共大欢喜，让我仔细看看

感觉因为灵梦每回合必定全体攻击1次所以反倒似乎没有博弈的问题了？似乎变得简单了？

 

最简单的情况考虑

早苗看到有k个1残机，能拿到1分，灵梦拿到k-1分

所以对于早苗来说，最好的情况是让残机保持1的等差数列

所以先sort一下应该是不亏的

另一种说法就是sort之后，退一万步说，早苗至少能拿到数列中不同元素个数的得分，这是最平凡的下限

 

sort之后如果有1残，那直接打了是绝对不会亏的（证明↓）

剧透

显然地，不打1残，后面的妖怪最多也只能移动1步，最多赚1分

只考虑1残的情况，对于k个1残，打了拿1分，不打拿0分。显然

反之有2残打2残是不会赚的（证明↓）

剧透

显然地，如果不打2残，后面的妖怪同样最多赚1分

如果有且仅有1个2残，打了之后会被灵梦收人头，分数+0。不打，灵梦打完之后可以自己收人头，分数+1

如果有k个2残，打了之后下一回合变成k-1个1残，不打变成k个1残。已知k >= 2，则k-1为正，参考上面1残不亏证明

综上2残不赚

但是对于2以上的残机，需要进一步判断

 

假定现在在j残机处有k个相同残机的妖怪，前一个空缺（指不存在该残机数妖怪）为i残机，那么早苗为了多拿1分，需要打j-i次

显然地，如果j>2i，早苗是拿不到这1分的，因为没等打过去呢，灵梦就先打没了

更进一步地，早苗如上所说的做法，只是为了多拿1分，因此在这个过程中，除非该回合拿不到分数，否则是不赚的

即，早苗为了多拿这1分，需要x回合

其中x == x以内不同元素个数 + (j - i)，换句话说就是为了多拿这1分，需要前面 (j - i)个空缺。顺带，从这句话可以得出，第一个出现重复妖怪的位置上是永远只能拿到1分的。我智障了，应该说第一个空缺是永远没法拿到分的。感觉似乎可以规约01背包了…………？

这个过程中，该妖怪一共掉残机 x + (j - i)，所以如果j 比 x + (j - i) 小，即x > i，则可以直接放弃这个妖怪了

 

最坏情况就可以用暴力动态规划了

四月 9, 2020，由yhz012修改

[yhz012]

4 分钟前, zengpingqq 说道:

我使用了个比较原始的办法，用C语言写了写：

直接冒泡或者快速等任何排序方法对A[n]重新排序，到处都能找到代码直接抄就行，直接略过，下面默认是从小到大排序好的

int k为当前最小的存活机序号-1，初始为0，int score = 0;然后遍历

 

写完后觉得如果用链表应该还简单点，懒得改了

问下变量i是什么？数组A的长度？

[yhz012]

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

华生你发现了盲点：问题的实质在于构造尽可能两两不相同的怪物残机数数列

顺带一提，这个题是个贪心题哦~

贪心就可以了么……那大概是我子问题定义错了……感觉我现在的定义没法保证单步最优必然全局最优……

我大概知道贪心的子问题是啥了……

不对好像还有点问题……

四月 9, 2020，由yhz012修改

[yhz012]

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

所以说，弄清楚贪心怎么做了么（笑

感觉似乎找到了方向，但是很快我就能举出来反例说明子问题的定义是不能保证全局最优的，感觉我似乎错过了什么关键证明

[yhz012]

58 分钟前, 随性而为 说道:

看着这个思路我找到了灵感，既然这样的话那就尽量使所有的怪物残机数都变成连续的数，比如1，2，3，4，5，早苗开始补刀，第一个死了，然后灵梦放AOE，变成1，2，3，4，然后循环……

如果是2，3，4，5，6这种的话，早苗可以选择拖延一轮，再如上所述。

当然这只是理想状态，可能会出现灵梦AOE放死了大部分敌人还没有出现连续的数的情况，这种写起来比较麻烦，还在思考中

总之，我觉得可以理解为早苗前期疯狂输出，之后划水，后期再疯狂补刀的情形

我们可以把早苗的行动分为3种

1.抢人头→打1残怪就完了

2.滑水→什么都不做

3.控血→打非1残怪，目的是让这个怪的残机数降低到一个空白的残机数的位置上，每次实际上是对数组内的某一个元素值-1

 

目前可以确定的是，如果可以抢人头，那么优先抢人头必然不亏 —— 引理1

（需要注意的是引理1只是不亏，或许不这么关注引理1有利于更好地构造算法）

 

另外对于灵梦的操作，我们可以用另一个角度看待，可能会方便理解一些

早苗的操作只会降低数组A内的元素值

灵梦的操作实际上可以视为在第k回合，把数组头移动到第一个大于k的元素上

 

首先毫无疑问我们可以把所有的不是空白的位置上标记为抢人头，而空白的位置上标记为滑水。这是我上面说的最平凡的解

 

根据引理1，我们知道如果要控血k次后得分，我们需要k个控血回合和1个抢人头回合，即共计k+1个回合原来是滑水的，我们需要从头开始把这k个原来是滑水的回合填上控血，然后第k+1个滑水的回合填上抢人头。

 

假定我们确实拿到了x个人头在位置C上（显然C内所有元素唯一），来源是A的子集B（显然BC的大小相等），我们必然需要控血sum(B)-sum(C)，且控血顺序不重要 —— 引理2

 

早苗打最高残机的怪血亏 —— 引理3 这个显然

 

引理3告诉我们，以理解为有max(A)个slot，然后往slot里塞上面3个行动就完了

四月 9, 2020，由yhz012修改

[yhz012]

46 分钟前, 随性而为 说道:

你说的数组头是类似于栈顶的作用吧……刚开始看的时候愣了好久……

具体数据结构其实我倒是觉得影响不大，我只需要这个数据结构可以支持以下行为即可：

1. 对内部元素根据value升序排序（可以不稳定排序，因为任何同value元素都是完全等价的）

2. 降低内部元素的value 1

3. 删除最小元素

 

最好做的方法大概是优先队列，一般最好做的实现方法是二叉堆？

（艹等下我怎么觉得好像有点邪道解法）

想多了，不存在的

  

46 分钟前, 随性而为 说道:

如果照我说的，那么早苗就是前期3，中期2，后期1喽

这句话我在考虑……或许这句话是做成贪心算法的关键……

四月 9, 2020，由yhz012修改

[yhz012]

7 分钟前, 随性而为 说道:

如果说是1，2，6，7，7……215，217，217的话前者控2次，后者控1次，但是必须得先控前者，因为先控后者的话就没机会控前者了

这个不影响，我姑且认为你的例子可能有一点点偏差，因为为了拿全所有人头你列的人头需要5个滑水位，所以我稍微改一下变成1,2,6,7,7,...,214,217,217。

你可以理解为假定我现在确定要拿1,2,6,7,214,216,217的人头那么我需要补刀1次，所以我需要在217前完成总计1次补刀就好了，至于在哪补，并不重要，这是我引理2说的内容

同理，如果我为了拿1,2,5,6,7,214,216,217，那我就需要在217前补3次，显然我现在有3,4,215给我补，至于具体我怎么补，根据引理2，肯定有方案补（即优先把前面的补了就好）

四月 9, 2020，由yhz012修改

[yhz012]

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

这个引理我觉得很重要，怎么打怪就变成了怎么往slot里塞东西，也就是说要把一个个怪“摊”到这个怪血量之前的那些slot上

然后，我觉得可以从控0次血开始一点点向上摊，先摊派控0次的，之后是控1次，直到无穷；如果发现有哪个怪摊不完所有的控血+击杀，就撤销这个怪的所有摊派（这个怪就不打了）

我似乎知道我智障在哪了

 

A.sort() #升序排列
slotNum = A[-1] #拿到A里最大的元素值，作为总的格子数

#计算各元素需要补刀数量
B = empty_like(A) #记录各元素需要补刀数
freeSpaceList = [] #记录可用划水位
index = 0

for value in range(1, slotNum + 1):
	#遍历A中的所有元素值，耗时O(|A| + max(A))
	if A[index] > value:
		#空，加入到划水位
		freeSpaceList.append(value)
	else:
		#A中值为value的第一个元素
		B[index] = 0 #不需要补刀
		index = index + 1 #移动到下一个元素
		while A[index] == value:
			#A中值为value的重复元素
			if freeSpaceList:
				#还有空余划水位可用
				lastFreeSpace = freeSpaceList.pop()
				B[index] = value - lastFreeSpace #计算补刀数
			else:
				#没空位我有什么办法嘛，这个人头彻底放弃了
				B[index] = -1
			index = index + 1 #移动到下一个元素


#开始填格子
tempLastIdx = 0 #记录目前预计最后一个人头的位置
tempFreeSpaceSize = 0 #记录目前可以操作的空间
score = 0 #记录目前的得分

for value in range(0, max(B) + 1):
	#从最好拿人头的（0补刀）开始，逐渐增加补刀数
	for index in range(len(B)-1, -1, -1):
		#倒序遍历所有元素
		if B[index] == value:
			#可以考虑拿人头了
			if tempLastIdx < index:
				#更新最后一个人头的位置
				tempFreeSpaceSize = tempFreeSpaceSize + (index - tempLastIdx) #因为最后一个人头位置增加了，增加了更多的操作空间
				tempLastIdx = idx
			if tempFreeSpaceSize > B[index] + 1:
				#有位置补刀+收人头
				tempFreeSpaceSize = tempFreeSpaceSize - (B[index] + 1)
				score = score + 1
			else:
				#没位置了，再往前也是一样要补刀的个数，一样不会有位置的
				break

基本算是按照py的语法写的，应该稍微改一些细节就能直接跑了，不过感觉应该有不少优化空间，这大循环写的我看着就疼

四月 9, 2020，由yhz012修改

[yhz012]

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

呃，嗯……

算法没问题没错，但是最大血量可以到1e8（盯

是的，这里我看着就疼，填格子的部分倒是可以先把B构造成key-value对，然后根据value sort一下然后能把下面的循环时间压到O(|A|)，上面的循环我还得考虑下……

 

某种意义上第一个求补刀数可以删掉，但是这样就要增加后面循环的量了……

后面的循环直接

A.sort()
A.reverse() #降序

usedSlot = {}
step = 0 #补刀数
slotNum = A[0] #总格子数

while A and slotNum >= step + 1:
	#A非空就继续填格子,或者所有格子填满了
	for a in A:
		#倒序遍历
		if a - step not in usedSlot:
			#有空位
			if slotNum > step + 1:
				#能补过来
				usedSlot = usedSlot + {a - step} #人头占位
				A.remove(a) #考虑过了，之后不用再看了
				score = score + 1
				slotNum = slotNum - (step + 1)
			else:
				#补不过来了，之后肯定都补不过来了
				return score
		else:
			#没空位，留着下一轮继续判断
			pass

 

四月 9, 2020，由yhz012修改

[yhz012]

13 小时前, 随性而为 说道:

我觉得这里应该是正序遍历

（讲道理引理2的B和C是什么我没看懂）

引理2的B和C都是和题目中的A一样的数组

其中B是A的子集，同时B中的每一个元素都可以在C中找到一个对应，这个对应要满足 b >= c

此外C中的元素全部唯一，没有重复元素

 

你可以理解为B是早苗的人头实际来源，C是早苗拿人头的回合

 

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

控血+打怪的时候，要优先选取离当前血量近的段，比如打35血怪要优先选取30-35段的那一个slot这样。

这点我同意，但是我头疼的是30-35有1个意味着我实际上是有，比如说30, 31, 32, 34, 35这样的一组数据的如果这时候我有一个重复35的要控血到33，我需要控2次就好了

但是如果我原来是30, 32, 33, 34, 35，我就需要控4次了……

感觉还是卡在了哪里……

 

啊我理解了，我实际上保存key-value对就好了，key是连续空白最后的位置，value是连续空白的长度

比如我写一个数组，里面存放这个key-value对，slot[(lastPos, size)]

这样我倒序的话，每次使用最大key的key-value对，消耗掉相应的value并降低key，value归零就丢掉这个kv对就完了

因为kv对是连续的，所以最坏被分割出(N+1)个kv对

 

判断对应slot是否被用了就直接找第一个大于index的key，然后看key-value是不是小于value就完了

四月 10, 2020，由yhz012修改

[yhz012]

1 小时前, 随性而为 说道:

如果是1，2，4，5，5，105，215，218，218，211，211

我觉得一开始的代码后面的循环这样改比较好，可能会解决这个问题吧（错了错了，还没改好）（改不动了，不会改）

for value in range(0, max(B) + 1):
	#从最好拿人头的（0补刀）开始，逐渐增加补刀数
	for index in range(0,len(B)-1):
		#正序遍历所有元素
		if B[index] == value:
			#可以考虑拿人头了
			tempFreeSpaceSize = tempFreeSpaceSize + (index - tempLastIdx) #因为最后一个人头位置增加了，增加了更多的操作空间
			tempLastIdx = index
			if tempFreeSpaceSize > B[index] + 1:
				#有位置补刀+收人头
				tempFreeSpaceSize = tempFreeSpaceSize - (B[index] + 1)
				score = score + 1
   	tempFreeSpaceSize=0
    	tempLastIdx=0

 

我决定用后面的这个代码了，因为一开始为了求B数组实在是太疼了1e8级别的跑起来真的太疼了