程序员进阶之算法练习（三十六）贪心
前言
万物皆贪心。
正文
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如逆水行舟，不练则废。
