时间限制：C/C++ 1秒，其他语言 2秒
64bit IO Format：%lld
1.GivenS=”…xxx..x….xxx.” and B = 7, the function should return 5.You can start by fixing the first three consecutive potholes for a cost of 4 obtaining the road:”……..x….xxx.”. Then, you can fix the last two potholes for a cost of 3.obtaining the road:”……..x….x…. The total cost is 7, which fits in the budgetand you fix 5 potholes in total.
2.Given S =”..xxxxx” and B =4, the function should return 3. One way is to fix the middle three potholes, which costs the whole budget and makes the road look as follows:”..x…x”. Alternatively, you could fix the first three potholes or the last three potholes.
3.Given S =”x.x.xxx.…x”and B =14, the function should return 6.You can fix all the potholes,which costs 2+2+4+2=10leaving you with the spare budget of 4.This fixes the entire road.
4.Given S =”.” and B =5, the function should return 0.There are no potholes to fix.
Write an efficient algorithm for the following assumptions
N is an integer within the range B is an integer within the range[0..200000]
string S consists only of charactersand x’.
package Microsoft // you can also use imports, for example: import ( "sort" )