程序员进阶之算法练习（三十六）贪心

前言

万物皆贪心。

正文

1.Filling Shapes

题目链接 题目大意： 有基础的三角图案（如下图-左边），需要填充到3xN的大矩形中，要求： 1、不留空隙； 2、没有重叠；

问，有多少种填充的组合方式。

输入： 数字n，表示3*N的大图案宽度；(1≤?≤60) 输出： 多少种填充方式。

Examples input 4 output 4 input 1 output 0

题目解析： n为奇数，则会出现填不满的情况（面积和不相等），此时为0； n为偶数，对于每3*2的6个格子，只有两种组合方式， 那么总共的方案是2^(n/2)的个数。

代码：

    int n;
    cin >> n;
    if (n % 2) {
        cout << 0 << endl;
    }
    else {
        lld ans = 1;
        for (int i = 0; i < n / 2; ++i) {
            ans *= 2;
        }
        cout << ans << endl;
    }

2.Plus from Picture

题目链接 题目大意： h行w列的字符，由'*'和'.'两种符号组成。 问字符中是否仅存在一个'+'号，加号的组成方式： 1、中心点是一个'*'号； 2、中心点的上下左右四个方向有一个或以上的连续'*'符号；

并且，除了这个'+'号，其他左右的字符都是'.'。

如果满足上面的条件，则输出"YES"，否则输出"NO"。

输入： 第一行是h, w; (1≤ℎ, ?≤500) 接下来是h行字符，每行有w个。

输出： 满足上面的条件，则输出"YES"，否则输出"NO"。

Examples
input
5 6
......
..*...
.****.
..*...
..*...
output
YES
input
3 5
..*..
****.
.*...
output
NO

题目解析： 先找到中心点，判断中心点是否为星号； 然后从四个方向去遍历，每个方向至少有1个星号，得到每个方向的星号； 总的星号是否等于图中的星号。 思考?： 另外一种简单的做法，以5个星号作为基础图案，遍历整个图找到一个最小的+号。 然后延伸去看长度，最后看是否等于所有星号字符数量。

代码地址。

3.Beautiful Lyrics

题目链接 题目大意： 一段悦耳的歌词有两行，每行有两个单词，并且要求： 1、第一行的第一个单词中元音数量，和第二行第一个单词相同； 2、第一行的第二个单词中元音数量，和第二行第二个单词相同； 3、第一行的第二个单词中的最后一个元音，和第二行第二个单词相同。

给出n个单词，问最多能拼出多少段悦耳的歌词，每个单词只能用一次。

输入： 第一行n，表示n个单词；（n<=10^5） 接下来n行，每行包括一个单词。 所有单词的字符总数不会超过10^6。

输出： 第一行数字m，表示m段歌词。 接下来是m段歌词，每段两行。

Examples input 14 wow this is the first mcdics codeforces round hooray i am proud about that output 3 about proud hooray round wow first this is i that mcdics am

题目解析： 先去除无关因素的影响，把每个单词的元音提取出来，分类成： 1、单词中元音的长度，分别是len=1、2、3.。。 2、相同长度的元音，分别有a/e/i/o/u 五种结尾的类型。

我们用vec[i][j]表示长度为i，结尾是第j个元音的字符串集合。

再来看看题目的要求，拼出最多的歌词，并且每个单词只能用一次。 而歌词的要求，可以表述为： 1、从相同长度字符串中，取出结尾相同的两个单词，作为第1、2行的第二个单词； 2、从相同长度字符串中，取出长度相同的两个单词，作为第1、2行的第一个单词；

从这里，我们可以得到一个贪心的策略： a.先两个两个的取出所有长度相同并且元音结尾相同的单词，得到x组，这是可能的最大歌词数量； b.从剩下的所有单词中，两两取出所有长度相同的单词，得到y组，ans=min(x, y)组； 如果x>y，那么剩下(x-y)组单词还可以两两组成歌词，此时还有ans+=(x-y)/2；

思考?： 当x>y时，能否取出x组中3个单词，取出1个步骤b剩下的单词，进行配对呢？ 答案是可以，但是没有必要。因为步骤b只会剩下0个或者1个某个长度的单词。

代码地址。

4. Split a Number

题目链接 题目大意： 有一个字符串str，表示一个数字（没有前导零)，现在需要把这个数字分成两个合法的数字，并且希望和尽可能的小。

输入： 第一行，数字n，表示字符串str的长度；(2≤n≤100000) 第二行，字符串str，表示数字； 输出： 最小的和。

Examples input 7 1234567 output 1801 input 3 101 output 11

题目解析： 先不考虑复杂度，对于每个位置pos，只要str[pos]不是字符0，那么就可以切分成两个字符串[0, pos) 和 [pos, n)两部分。 那么可以枚举每一个位置，计算一遍数字的和，最终得到一个最小的数字和。 枚举复杂度是O(N)，分割数字和计算数字和是(N)，总的复杂度是O(N^2)； 因为n最大可以为10w，那么这个复杂度是不可以接受的。

容易知道，很多位置的分割，是不可能成为最小和的值。比如说字符串1234567，如果分割成12+34567或者1+234567是明显重复的计算。 由贪心的思想可以知道，分割出来的字符串a、b的长度应该尽可能接近。 对于长度为n字符串，分割成长度为n/2和n-n/2 ，或者(n+1)/2和n-(n+1)/2的组合是最好的。

那么是否枚举这个情况即可？

并不是！因为存在一个数字0的情况。比如说数字123000321，中间的位置都是0。 综合上面的考虑，我们可以将n/2向左延伸，直到找到一个不为零的数字，作为分割点； 同样的，将(n+1)/2向右延伸，知道找到一个不为零的数字，作为分割点。

然后从上面的两个可能，选择一个最小的值。

时间复杂度O(N)；

代码：

    int n;
    cin >> n;
    string str;
    cin >> str;
    
    /*
      所有的切分都是[0, t-1], [t, n)  不同的是t的位置不同
     要求，str[t]不能为字符0.
     
     t可以是n/2,n/2+1等
     */
    
    int x = (n + 1) / 2, y = n / 2;
    string ansX = str, ansY = str;
    
    while (x < str.length() && str[x] == '0') {
        ++x;
    }
    if (x < str.length()) {
        ansX = getSplitSum(str, x);
    }
    
    while (y >= 0 && str[y] == '0') {
        --y;
    }
    if (y >= 0) {
        ansY = getSplitSum(str, y);
    }
    
    cout << getMinStr(ansX, ansY) << endl;

具体方法的实现。

总结

题目1：根据题目的特性，可以看出三角形无法填充33的矩形，只能填充32的矩形，那么大问题就可以划分成多个小问题； 题目2：思路比较明显，重点是在于如何找到中心点，我采用的是看每一行每一列的累积星号数量，求交点；别人直接判断一个最小星号，这种做法更加便捷、快速、简练； 题目3：题目的要求看起来很复杂， 通过分析、细化、抽象，提示要素就只有长度、结尾类型两个参数；按照我们归类出来的参数，进行聚合就很容易决策； 题目4：直接的想法很容易想到，比如说从中间分开；但是考虑到前导零的case，用合适的表达方式，会更加容易去计算。

Coding如逆水行舟，不练则废。