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

[Mr.K 018]

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

第1期 异变退治

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

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

输入

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

输出

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

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

 

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

召唤阵：

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

 

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

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

[zengpingqq]

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

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

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

for(;0 == A;)

{

    for(m=k;m<i;m++)

        {

            A[m]--;

            if(1 == A[m])

            {    

                Score++;

                break;

             }

        }

    if(m<i)

        for(;m<i;m++){

             A[m]--;

             if(0 == A[m]) k++;

        }

    else

         A[k]--;

}

printf("Zhe score is %d",&Score);

 

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

四月 9, 2020，由zengpingqq修改

[yhz012]

4 分钟前, zengpingqq 说道:

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

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

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

 

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

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

[zengpingqq]

4 分钟前, yhz012 说道:

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

题里出现的A的i,至于不用N的原因是在计算机里都是从0开始的，不然都需要写成N-1

[Mr.K 018]

17 分钟前, zengpingqq 说道:

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

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

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

//code

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

阁下的思路是？

[Mr.K 018]

1 小时前, yhz012 说道:

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

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

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

[yhz012]

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

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

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

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

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

不对好像还有点问题……

四月 9, 2020，由yhz012修改

[Mr.K 018]

1 小时前, yhz012 说道:

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

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

不对好像还有点问题……

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

[inuisanaa]

来了来了

这又是什么东西

走了走了

[ZERC]

1 分钟前, inuisanaa 说道:

来了来了

这又是什么东西

走了走了

彼此彼此，我也是蒙蔽的

继续修炼吧...

[inuisanaa]

刚刚, ZERC 说道:

彼此彼此，我也是蒙蔽的

继续修炼吧...

这回我来.....你 怎 么 还 不 睡 觉

[Mr.K 018]

3 分钟前, inuisanaa 说道:

来了来了

这又是什么东西

走了走了

 

1 分钟前, ZERC 说道:

彼此彼此，我也是蒙蔽的

继续修炼吧...

别嘛wwww

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

[ZERC]

刚刚, inuisanaa 说道:

这回我来.....你 怎 么 还 不 睡 觉

的确www

再见www

我看好你www

[yhz012]

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

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

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

[Mr.K 018]

1 分钟前, yhz012 说道:

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

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

[随性而为]

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，由随性而为修改

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

[随性而为]

21 分钟前, yhz012 说道:

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

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

2.滑水→什么都不做

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

 

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

 

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

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

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

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

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

[yhz012]

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

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

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

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

2. 降低内部元素的value 1

3. 删除最小元素

 

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

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

想多了，不存在的

  

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

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

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

四月 9, 2020，由yhz012修改

[Mr.K 018]

1 小时前, yhz012 说道:

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

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

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

[随性而为]

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

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

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

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

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

[Mr.K 018]

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

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

不矛盾啊

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

[随性而为]

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，由随性而为修改