2016级算法第四次上机-D.AlvinZH的1021实验plus

978 AlvinZH的1021实验plus

思路

贪心，中等题。

使用miss变量表示未覆盖的最小数字，初始值为1。

初始覆盖区间为[1,miss)，目标是覆盖[1,m]，即miss需要大于m。

需要比较miss和数组里没有使用的数字中最小的数字x（所以需要先给数组排序。

• miss更小：没有一个组合可以满足需要的值，需要插入该值，即插入miss，这时覆盖区间变成 \([1,miss<<1)\) 。
• miss更大：当前可以覆盖[1,miss)，加上此值，覆盖区间变为 \([1,miss+x)\) 。

循环终止条件：miss > m。

以下是番外内容：

多位同学问我为什么WA，原因是没有看到砝码只能放在同一边，受到上一题的影响（助教窃笑，小伙子还是不够细啊。

还有同学问OJ是不是有问题，明明应该是WA却提示TLE，原因是数组数字在int范围内，miss可能会超过int，计组里面有讲到INT32_MAX+1会变成什么，答案是INT32_MIN，所以你的while相当于无限循环，不TLE才怪。

分析

本题的贪心在于，为了最快接近目标数m，每次都最大化覆盖范围。

再说一下贪心，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。

参考代码一

//

// Created by AlvinZH on 2017/11/19.

// Copyright (c) AlvinZH. All rights reserved.

//

#include <cstdio>

#include <algorithm>

using namespace std;

int n, m;

int FM[1005];

int main()

{

    while(~scanf("%d %d", &n, &m))

    {

        for (int i = 0; i < n; ++i)

            scanf("%d", &FM[i]);

        sort(FM, FM + n);

        int ans = 0;

        int pos = 0;

        long long miss = 1;

        while(miss <= m)

        {

            if(pos < n && FM[pos] <= miss) {

                miss += FM[pos];

                pos++;

            }

            else {

                ans++;

                miss <<= 1;

            }

        }

        printf("%d\n", ans);

        /* 简单替换

        int ans = 0, pos = 0;

        for (long miss = 1; miss <= m; ans++)

            miss += (pos < n && FM[pos] <= miss) ? FM[pos++] : miss;

        printf("%d\n", ans - pos);

        */

    }

}