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

[随性而为]

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

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

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

看着这个思路我找到了灵感，既然这样的话那就尽量使所有的怪物残机数都变成连续（应该是必为连续的，不然相同的两个没办法一起收）的数，比如1，2，3，4，5，早苗开始补刀，第一个死了，然后灵梦放AOE，变成1，2，3，4，然后循环……

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

理想状态下可以先使1号敌机-0，2号敌机-1，3号敌机-2……

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

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

（现在感觉我说的都是废话）

四月 9, 2020，由随性而为修改

[随性而为]

21 分钟前, yhz012 说道:

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

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

2.滑水→什么都不做

3.控血→打非1残怪，目的是让这个怪的残机数降低到一个空白的残机数的位置上

 

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

 

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

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

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

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

四月 9, 2020，由随性而为修改

[随性而为]

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

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

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

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

[随性而为]

35 分钟前, yhz012 说道:

这个不影响，我姑且认为你的例子可能有一点点偏差，因为为了拿全所有人头你列的人头需要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，肯定有方案补（即优先把前面的补了就好）

 

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

不矛盾啊

相当于提前决定在216的时候控217，3和4的时候控那个7

懂了，但总是觉得哪里怪怪的，可能我还没有完全看透吧，我再研究研究，没准能找出反例

四月 9, 2020，由随性而为修改

[随性而为]

3 小时前, yhz012 说道:

 

 

	for index in range(len(B)-1, -1, -1):
		#倒序遍历所有元素

 

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

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

四月 9, 2020，由随性而为修改

[随性而为]

6 小时前, yhz012 说道:

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

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

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

 

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

 

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

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

感觉还是卡在了哪里……

如果是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

 

四月 10, 2020，由随性而为修改