贪心算法之猴子吃香蕉(Monkeys and Bananas) ??这道题是比较简单的贪心算法的题，首先我们来看题目： 问题描述 **Problem Description**Given an array of size n that has the following speci?cations:Each element in the array contains either a monkey or a banana.Each monkey can eat only one banana.A monkey cannot eat a banana which is more than K units away from the monkey.We need to ?nd the maximum number of bananas that can be eaten by monkeys. 输入 **Input**Two lines.The first line contains an array of 香港vps size n contain chars ‘B’ (represent Banana) or ‘M’ (represent Monkey). n >= 0.The second line contains a integer K, K >= 0. 输出 **Output**An integer, the maximum number of bananas can be eaten by monkeys 解题思路
??因为题目要求了一个香蕉最多只能让一个猴子吃，一个猴子也最多吃一个香蕉，因此我们采用投票法的思想，即一个猴子如果吃到了香蕉，我们就把猴子由”M”变成”A”,也就是这个猴子吃完一个香蕉之后就再也不能吃香蕉了。
??具体的做法是首先遍历整个MB数组，如果这个数组元素是”B”，则以这个”B”为圆心，以k为半径，1为步长，搜索”M”，如果这个范围内找到”M”,则把这个”M”变成”A”,跳出循环体，进行下一个循环。
C++源代码 /*date:2019年11月28日 Author: Chauncy_xu*/#include<string>using namespace std;int main(){ string MB; int k,sum=0,l; cin>>MB; cin>>k; l=MB.length(); for(int i=0;i<l;i++) { if(MB[i]==’B’) { for(int j=-k;j<=k;j++) { if((i+j>=0)&&(i+j<=l)&&(MB[i+j]==’M’)) { MB[i+j]=’A’; sum+=1; break; } } } } cout<<sum; return 0;}
不足之处，多多指教。
