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

[Mr.K 018]

好像昨天的公测太数学了，今天题目简单一点！

第1期 异变退治

本题来源：HDU4976, 由BIT112013****改编

在一次异变中，早苗酱和灵梦展开退治大赛。假设现在一共有N个妖怪，每个妖怪残机数为A。由早苗酱开始两个人轮流行动。早苗酱每次能伤害至多一个妖怪，将其残机数减一（也可以选择不作为）；灵梦每次一定会伤害所有妖怪，全体残机数减一。当有一个妖怪的残机数在某人的回合被减至0或更少时，这个妖怪被退治（消失），同时该人得一分。现在早苗想知道自己最多能拿多少分（补刀数）。

输入

只有一组测试用例，第一行为N()，表示妖怪的个数，接下来一行有N个数，分别表示每个妖怪的初始残机数A()。

输出

输出一行，其中有一个整数，表示早苗最高可能的得分。

给出算法的同时，试一试证明算法的正确性！

 

才发现自己忘掉了什么，赶紧补上

召唤阵：

@ZERC @inuisanaa @随性而为 @NianRuoshui  @魍魉QAQ @提辖 

 

四月 9, 2020，由Mr.K 018修改

[Mr.K 018]

17 分钟前, zengpingqq 说道:

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

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

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

//code

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

阁下的思路是？

[Mr.K 018]

1 小时前, yhz012 说道:

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

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

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

[Mr.K 018]

1 小时前, yhz012 说道:

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

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

不对好像还有点问题……

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

[Mr.K 018]

3 分钟前, inuisanaa 说道:

来了来了

这又是什么东西

走了走了

 

1 分钟前, ZERC 说道:

彼此彼此，我也是蒙蔽的

继续修炼吧...

别嘛wwww

来康康题嘛，做一做你不会吃亏，做一做你不会上当（笑

[Mr.K 018]

1 分钟前, yhz012 说道:

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

没事没事，说出来也可以让大家来一起打磨啊

[Mr.K 018]

1 小时前, yhz012 说道:

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

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

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

[Mr.K 018]

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

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

不矛盾啊

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

[Mr.K 018]

5 分钟前, yhz012 说道:

我似乎知道我智障在哪了

 

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的语法写的，应该稍微改一些细节就能直接跑了

呃，嗯……

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

这个算法都到这了，我觉得优化一下没啥问题，因为我们不在乎每一个slot被用来干啥了，只关心有多少slot可以用，这样的话是能把存储量压到1e5的

四月 9, 2020，由Mr.K 018修改

[Mr.K 018]

2 小时前, yhz012 说道:

usedSlot = {}

这个usedSlot我觉得不用保存成集合，我们可以只知道当前有多少个slot可以用就能进行下去了。

（删掉了一些错误信息）

我们只要保存每个血量段有多少个slot可以用，比如10血到20血的分段我有3个slot可以用，20-30没有，30-35有1个这样等等

分段的依据是怪，比如上例中这么分段的原因会是因为有10血、20血、30血、35血的怪。控血+打怪的时候，要优先选取离当前血量近的段，比如打35血怪要优先选取30-35段的那一个slot这样。

这样一来，程序的复杂度应该就降到n^2了？我肉眼看是n^2

四月 9, 2020，由Mr.K 018修改