#LQ1095. 移除棋子

移除棋子

题目描述

nn颗棋子排成一排,每颗棋子为白色(用1表示)或黑色(用0表示)。

每次可以选择从最左端或者最右端移除一颗棋子,最终使剩余棋子中白色棋子的数量为mm

给定两个整数nnmm,及nn颗棋子的颜色排列。

请计算最少要移除多少颗棋子,才能使剩余棋子中白色棋子的数量为mm;如果无法实现该目标,输出-1

例1:n=8m=2n=8,m=2,8颗棋子的颜色分别是01011001,要使剩余棋子中白色棋子的数量为2,最少需要移除3颗棋子,移除方案如下:

第一次,移除最右端的棋子,移除后剩余棋子的颜色分别是0101100;

第二次,移除最左端的棋子,移除后剩余棋子的颜色分别 是101100;

第三次,移除最左端的棋子,移除后剩余棋子的颜色分别是01100:

此时,剩余棋子中白色棋子的数量为2。

例2:n=5m=3n=5,m=3,5颗棋子的颜色分别是10010,无论如何移除棋子,都不能使剩余棋子中白色棋子的数量为 3。

输入描述:

第一行输入两个整数 nmn,m,分别表示初始棋子数量和目标白色棋子数量,整数之间以一个空格隔开;

第二行输入nn个整数(整数为1或0,1表示白色棋子,0表示黑色棋子),表示从左到右每颗棋子的颜色,整数之间以一个空格隔开。

输出描述:

输出一个整数,表示最少要移除多少颗棋子,才能使剩余棋子中白色棋子的数量为mm;如果无论如何移除棋子,都不能使剩余棋子中白色棋子的数量为mm,则输出-1

8 2
0 1 0 1 1 0 0 1
3

提示

(1nm106)(1≤n,m≤10^6)