yhz012 发布于四月 9, 2020 分享 发布于四月 9, 2020 (已修改) · 只看该作者 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修改 链接到点评
Mr.K 018 发布于四月 9, 2020 作者 分享 发布于四月 9, 2020 (已修改) · 只看该作者 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和寒幼藏在半夜盗取清禾的传国玉玺时，无意中挖出了清禾祖传的3DS，卖出手后获得了奖励8节操 链接到点评
yhz012 发布于四月 9, 2020 分享 发布于四月 9, 2020 (已修改) · 只看该作者 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修改 链接到点评
随性而为 发布于四月 9, 2020 分享 发布于四月 9, 2020 (已修改) · 只看该作者 3 小时前, yhz012 说道: for index in range(len(B)-1, -1, -1): #倒序遍历所有元素 我觉得这里应该是正序遍历 （讲道理引理2的B和C是什么我没看懂） 四月 9, 2020，由随性而为修改 随性而为路过听到路过酱的歌声，不小心被路过的鸡仔绊倒，受到了路过酱的赔偿金2节操 链接到点评
Mr.K 018 发布于四月 9, 2020 作者 分享 发布于四月 9, 2020 (已修改) · 只看该作者 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修改 链接到点评
yhz012 发布于四月 9, 2020 分享 发布于四月 9, 2020 (已修改) · 只看该作者 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修改 链接到点评
随性而为 发布于四月 10, 2020 分享 发布于四月 10, 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，由随性而为修改 随性而为收和谐资源时被小萝莉围观良心发现失去-2节操 1 链接到点评
yhz012 发布于四月 10, 2020 分享 发布于四月 10, 2020 · 只看该作者 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级别的跑起来真的太疼了 1 链接到点评
推荐贴