[编程题]贪吃的小Q-算法题记录

前几天隔壁宿舍同学在刷算法题，串门的时候看到了这道有趣的题，记录一下。 原题目是这样的： 链接：https://www.nowcoder.com/questionTerminal/d732267e73ce4918b61d9e3d0ddd9182?orderByHotValue=1&page=1&onlyReference=false 来源：牛客网 小Q的父母要出差N天，走之前给小Q留下了M块巧克力。小Q决定每天吃的巧克力数量不少于前一天吃的一半，但是他又不想在父母回来之前的某一天没有巧克力吃，请问他第一天最多能吃多少块巧克力

输入描述:

每个输入包含一个测试用例。
每个测试用例的第一行包含两个正整数，表示父母出差的天数N(N<=50000)和巧克力的数量M(N<=M<=100000)。

输出描述:

输出一个数表示小Q第一天最多能吃多少块巧克力。

3 7

4

一开始打算找规律，使用2的n次方进行分配，最后也没有得出一个好的解法（虽然已经很接近了），于是看了一下牛客的参考答案，主要是两种解法：

二分查找法：

非常暴力的方法，意料之外情理之中。需要的结果为“第一天最多可以吃多少个”，这个值一定在0与巧克力总数M之间。于是可以在[0,M]区间内进行二分查找。复杂度为O(logM·N)，代码如下：

//@小冲冲

#include
using namespace std;
int n,m;
//计算第一天吃s个巧克力一共需要多少个多少个巧克力
int sum(int s){
    int sum=0;
    for(int i=0;i<n;i++){ sum+=s; s=(s+1)>>1;//向上取整
    }
    return sum;
}
//二分查找
int fun(){
    if(n==1) return m;
    int low=1;
    int high=m;//第一天的巧克力一定是大于等于1小于等于m的
    while(low<high){ int mid=(low+high+1)>>1;//向上取整
        if(sum(mid)==m) return mid;//如果第一天吃mid个巧克力，刚刚好吃完所有巧克力，那么直接返回
        else if(sum(mid)<m){ low=mid; }else{ high=mid-1; } } return high; } int main() { cin>>n>>m;
    int res=fun();
    cout<<res<<endl;
    return 0;
}

但是我个人觉得这个想法不太elegant，复杂度仍有一些高，于是再往下翻，找到一个比较有意思的解法，跟我一开始的想法差不多。他没有标明他的方法，我给他随便起个名字：

逐次分配法：

他的思路如下：

1. 首先，每天分配一颗巧克力
2. 计算得到剩余的可分配巧克力
3. 按照2的N次方的顺序给各天分配，如：可分配的有7颗，则第一天分4个，第二天分2个，第三天分1个。
4. 计算剩余的巧克力数量，如果还有剩余，跳转到2
5. 没有剩余可分的巧克力，则完成分配。

代码如下：

//@域外創音
#include
#define MAX_INDEX 17
int power2[] = {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072};
int main()
{
    int n,m;
    std::cin>>n>>m;
    //只有1天时直接输出
    if(n==1){std::cout<<m<<std::endl;return 0;} //初始分配：每天最少吃1块     
    int alignable = m-n; 
    int result = 1; //如果可以某种power2[i]-1的方式分配，便进入。具体的分配是：第一天多吃power2[i-1]块，第二天多吃power2[i-2]块，依此类推。 
    //这样一来，只要每个追加分配所对应的i不重复，每天吃的块数就依然能符合要求，因为第j天吃的块数最多等于power2[从i-j到0]+1，一定大于power2[从i-j-1到0]的二倍。 
    for(int i=MAX_INDEX-1;i>=0;i--)if(alignable>=power2[i]-1)
    {
        result+=power2[i-1];
        alignable -= (power2[i]-1);
    }
    std::cout<<result<<std::endl;
    return 0;
}

这个代码非常的有意思，它可以把复杂度减少到O(log(m))，并且它还通过了所有测试用例。但是，作为预备役测试猿，我找到了它一个bug（笑）。当输入用例为（3天，20块巧克力）时，跑出来的结果是10，但是实际上，可以得到（11，6，3）的分配策略，与其得到的结果不符。使用二分查找法得出的结果也为11.问题出在哪里呢，通过代码走读很容易定位到问题出在18行：

alignable -= (power2[i]-1);

以（3天，20块）为用例，逐步推演，即可看到问题是怎么样发生的：

在第一轮分配的时候，@域外創音 的方法是，默认认为分配了pow(2,n)-1颗，而不是实际分出去的颗数。在此用例中，假如有4天或以上，分配列为（8，4，2，1），alignable -= 15无疑是正确的，但是当只有3天时，则会给不存在的第四天分配了一颗，从而导致最终结果的错误。

更正的方法也很简单，就是把alignable -= (power2[i]-1);改为alignable -= actually_assigned即可，而actually_assigned值的计算可以由代码中的i与天数n联合得出。

经过修改的代码如下，通过了牛客网的OJ所有测试用例，暂未发现未通过的其它反例。

#include<iostream>
#define MAX_INDEX 17
int power2[] = {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072};
int main()
{
    int n,m;
    std::cin>>n>>m;
    //只有1天时直接输出
    if(n==1){std::cout<<m<<std::endl;return 0;} //初始分配：每天最少吃1块
    int alignable = m-n;
    int result = 1; //如果可以某种power2[i]-1的方式分配，便进入。具体的分配是：第一天多吃power2[i-1]块，第二天多吃power2[i-2]块，依此类推。
    //这样一来，只要每个追加分配所对应的i不重复，每天吃的块数就依然能符合要求，因为第j天吃的块数最多等于power2[从i-j到0]+1，一定大于power2[从i-j-1到0]的二倍。
    for(int i=MAX_INDEX-1;i>=0;i--)if(alignable>=power2[i]-1)
        {
            if(i>0)//防止越界
                result+=power2[i-1];
            int assigned = 0;
            if(i>n)
                assigned = (power2[i]-1) - (power2[i-n]-1);
            else
                assigned = (power2[i]-1);
            alignable -= assigned;
        }
    std::cout<<result<<std::endl;
    return 0;
}