学线，集合！(by zwn)

难度：简单 tag：数组，计算，送分题

又到了一年一度的迎新季，由于学线福利待遇好，又有新办公室，导致今年迎新展台异常火爆。孔站火速召集学线同学前来帮忙。现在把前来帮忙的同学的位置标记在数轴上，每个同学的位置也存在数组 locate 当中。

孔站可以对 任何同学 执行下面两种操作之一（不限操作次数，0 次也可以）：

将任意一个同学向左或者右移动 2 个单位，代价为 0。
将任意一个同学向左或者右移动 1 个单位，代价为 1。

输入数组locate，返回将所有同学移动到同一位置（任意位置）上所需要的最小代价。

最开始的时候，同一位置上也可能有两个或者更多的同学哦。

输入样例

1
[1,2,3]

输出样例

1
1
1
解释：第二个筹码移动到位置三的代价是 1，第一个筹码移动到位置三的代价是 0，总代价为 1。

思路：最基础的贪心思想

贪心算法：

（英语：greedy algorithm），又称贪婪算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。比如在旅行推销员问题中，如果旅行员每次都选择最近的城市，那这就是一种贪心算法。

贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。

贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。

贪心法可以解决一些最优化问题，如：求图中的最小生成树、求哈夫曼编码……对于其他问题，**贪心法一般不能得到我们所要求的答案。一旦一个问题可以通过贪心法来解决，那么贪心法一般是解决这个问题的最好办法。**由于贪心法的高效性以及其所求得的答案比较接近最优结果，贪心法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。在不同情况，选择最优的解，可能会导致辛普森悖论（Simpson’s Paradox），不一定出现最优的解。

基本步骤：

步骤1：从某个初始解出发；
步骤2：采用迭代的过程，当可以向目标前进一步时，就根据局部最优策略，得到一部分解，缩小问题规模；
步骤3：将所有解综合起来。

栗子：

找零钱问题

假设你开了间小店，不能电子支付，钱柜里的货币只有 25 分、10 分、5 分和 1 分四种硬币，如果你是售货员且要找给客户 41 分钱的硬币，如何安排才能找给客人的钱既正确且硬币的个数又最少？

这里需要明确的几个点：
1.货币只有 25 分、10 分、5 分和 1 分四种硬币；
2.找给客户 41 分钱的硬币；
3.硬币最少化

（回顾一下上文贪婪法的基本步骤，1，2，3）

1.找给顾客sum_money=41分钱，可选择的是25 分、10 分、5 分和 1 分四种硬币。能找25分的，不找10分的原则，初次先找给顾客25分；
2.还差顾客sum_money=41-25=16。然后从25 分、10 分、5 分和 1 分四种硬币选取局部最优的给顾客，也就是选10分的，此时sum_money=16-10=6。重复迭代过程，还需要sum_money=6-5=1,sum_money=1-1=0。至此，顾客收到零钱，交易结束；
3.此时41分，分成了1个25，1个10，1个5，1个1，共四枚硬币。

但是，我们再回顾一下第一个事例问题

现在问题变了，还是需要找给顾客41分钱，现在的货币只有 25 分、20分、10 分、5 分和 1 分四种硬币；该怎么办？

按照贪心算法的三个步骤：

1.41分，局部最优化原则，先找给顾客25分；
2.此时，41-25=16分，还需要找给顾客10分，然后5分，然后1分；
3.最终，找给顾客一个25分，一个10分，一个5分，一个1分，共四枚硬币。

是不是觉得哪里不太对，如果给他2个20分，加一个1分，三枚硬币就可以了呢？^_^;

对于本题：

既然要贪心，即保证总开销值最小，那么对于每一次的移动选择，我们如果能选择开销为0的移动方式，就绝对不选择开销为1的移动方式。因此我们尽量通过方式一先将尽量多的同学移动到一起，在剩下的同学无法再通过方式一来移动到同一位置的时候，尽量使用最少次数的方式二来移动。

那么，不妨先将处于奇数位的同学移动到1的位置，偶数位都移动到2，在此过程中，0开销，然后再将两组同学合并，哪组同学人数少就移动到另一组里去，仍然是一步贪心。

总结：

贪心算法的优缺点

优点：简单，高效，省去了为了找最优解可能需要穷举操作，通常作为其它算法的辅助算法来使用；

缺点：不从总体上考虑其它可能情况，每次选取局部最优解，不再进行回溯处理，所以很少情况下得到最优解。

（样例选自小白算法）

吃果冻(by zwn)

难度：一般 tag： String操作 流程控制 基本数据类型

众~~~所周知，ycjj最喜欢吃果冻。今天ycjj兴致勃勃地去超市买果冻，但现在超市售货机出现了乱码，老板表示只要ycjj能写程序找对乱码中“果冻”出现的次数就可以让ycjj免费吃相应数量的果冻，但ycjj表示：我都转专业了你竟然还让我写代码，你礼貌吗？于是找到了你来帮她写代码，并保证会根据代码的正确性给予一定的oj分数作为回报。现在有多行乱码（字符串），老板保证每行字符串不含空格，请你输出其中“果冻”这两个字出现的次数。

输入样例：

1
2
a14&&果冻*guhj
b果冻%hask果冻

输出样例

1
3

思路：

老生常谈的一类题目，对于java来说特别友好，可用的方法有很多，但基本都绕不开split方法。

一种方法是采用字符串循环截取，对于输入的每一行，只要该行仍然包含目标字符串，就将该行字符串截取为从该行最前面的目标字符串的下一个字符到字符串最后的一个子串，同时次数++，如此依次处理各行字符串即可。

另一种方法可以采用字符串直接截取，对一行字符串，如果包含目标字符串，直接调用split将其划分为字符串数组，将数组长度减一即为包含的目标字符串个数。但有一个问题，如果目标字符串在开头或结尾，split划分出来的字符串数组中不会含有空字符串，导致再使用上述方法会导致答案错误。比如:

1
2
3
String str = "果冻啊果冻真好";
System.out.print(Arrays.toString(str.split("果冻")));
//["啊","真好"]

那该如何解决呢？方法有很多，我最喜欢的方法是拼接无关子串，也就是在每行字符串的两端加上不相关的字符串，然后再split就好了。

wngg爬八楼(by zwn)

众所周知，wngg住在八楼，每天都要爬好多楼梯，wngg发现自己每天要爬M阶楼梯，由于wngg腿长，wngg可以一次上两级楼梯，但累了也可以一次上一级，即每次上一级楼梯或者两级楼梯都可以。wngg突发奇想让你来算算他爬楼梯爬到M级一共有多少种方法。

初始时wngg在第一级台阶，并且认为爬到第一级一共有0种方法。同样地也可以知道上到第二级有1种方法。

Input

输入数据首先包含一个整数N，表示测试实例的个数，然后是N行数据，每行包含一个整数M（1<=M<=40）,表示楼梯的级数。

Output

对于每个测试实例，请输出不同走法的数量，共N行。

Sample Input 1

1
2
3
2
2
3

Sample Output 1

1
2
1
2

Sample Input 2

1
2
1
8

Sample Output 2

1
21

Hint

这是高中常见，算法入门，几乎每本编程书都会讲的一类问题。建议逆向思考，正向编程。

思路：斐波那契数列

逆向思考，正向编程，循环就能解决。逆向思考，逆向编程，递归。

这道题想明白了就很简单，除了几个小坑。

都说了要逆向思考，指的是我们不要从第一级台阶考虑如何上到第n级台阶，而是要考虑，在第n级台阶的时候，我是从哪里上来的。那么很明显，只能从第n-1级或者n-2级台阶走到第n级台阶，也就是说，走到第n级台阶的方法就是走到第n-1级和n-2级台阶的方法的求和，那么一直递推到第1级台阶就很显然是一个斐波那契数列，但是如果要从第n级台阶开始递推，显然是一个递归问题，但是既然知道了是斐波那契数列，为啥不直接从第一级台阶开始用循环进行递加呢，难度瞬间降低，这就是所谓的正向编程。

那么，坑在哪？

首先，读题问题。wngg初始在第一级台阶，并且认为爬到第一级一共有0种方法。我都给你加粗了你都看不见这能赖谁。

其次，一个思维惯性的小坑。很多情况时往往是一些特殊情况我们没有考虑到位而导致无法AC。这道题，第一、第二级台阶是特殊情况需要单独处理，这是一般斐波那契数列的惯性思维，但也恰恰会忽略，其实第三极台阶也需要特殊处理。

走到第一级，方法有0种。第二级，方法有1种，第三级，方法有2种，从第四级开始才是斐波那契数列。（我的样例里面都直接写了你还做不对）