牛客真题编程——day15

编译环境：c++

1、ZJ3 编程题2

描述

有一个仅包含’a’和’b’两种字符的字符串s，长度为n，每次操作可以把一个字符做一次转换（把一个’a’设置为’b’，或者把一个’b’置成’a’)；但是操作的次数有上限m，问在有限的操作数范围内，能够得到最大连续的相同字符的子串的长度是多少。

算法思想：

运用滑动窗口的思想，首先对字符串进行遍历，先取得一个子序列中最多含有（m个a/m个b），也就是让子序列中a或者b的操作次数刚好临界m时。然后滑动窗口，只有当再次满足a个数和b的个数都大于m，且其中一个字符恰好超过m的条件时，再次比较子序列长度。遍历完成后取得满足操作次数内，最长的子序列。

代码部分实现：

2、钓鱼比赛

描述：

ss请cc来家里钓鱼，鱼塘可划分为n＊m的格子，每个格子有不同的概率钓上鱼，cc一直在坐标(x,y)的格子钓鱼，而ss每分钟随机钓一个格子。问t分钟后他们谁至少钓到一条鱼的概率大？为多少？

算法思想：

题目其实是一道基础数学题，根据概率问题，t分钟后每个人钓到鱼的概率可以标识为P事件，有P=1-(1-P（ss/cc）)^t，而对于Pcc事件，可知他每分钟钓到鱼的概率就是坐标元素值，而Pss随机选择钓口，那么他的每分钟钓到的概率就是所有格子的概率相加之和的平均值。

代码部分实现：

3、年会抢玩偶游戏

描述：

某公司年会上，组织人员安排了一个小游戏来调节气氛。游戏规则如下：

N个人参与游戏，站成一排来抢工作人抛来的M个小玩偶。为了增加游戏的趣味和难度，规则规定，参与游戏的人抢到的礼物不能比左右两边的人多两个或以上，否则会受到一定的惩罚。游戏结束时拥有玩偶最多的人将获得一份大奖。

假设大家都想赢得这份大奖，请问站在第K个位置的小招在赢得游戏时，最多能拥有几个玩偶？

算法思想：

要想使得第k位的小招在不违反规则的情况下赢得游戏，那么小招与相邻参与人员的玩偶数只能依次递减1个。让小招先拿最多的玩偶数，然后依次递减遍历左右两边的参与人员，依次加上所有人的玩偶个数。一开始玩偶的总数肯定要大于实际玩偶的个数，然后依次让小招的玩偶数循环递减，当有一次循环分配的玩偶个数不超过实际玩偶个数时，此时就是最优的分配方案，可以使得小招在规则下，得到最多的玩偶。打印输出即可，注意异常输入的数据处理。

代码部分实现：