1529: 移除棋子

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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

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

给定两个整数 n 和 m,及 n 颗棋子的颜色排列。

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

例 1:

n = 8,m = 2,8 颗棋子的颜色分别是 0 1 0 1 1 0 0 1,

要使剩余棋子中白色棋子的数量为 2,最少需要移除 3 颗棋子,

移除方案如下:

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

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

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

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

例 2:

n = 5,m = 3,5 颗棋子的颜色分别是 1 0 0 1 0,

无论如何移除棋子,都不能使剩余棋子中白 色棋子的数量为 3。  

Input

第一行输入两个整数 n,m

分别表示初始棋子数量和目标白色棋子数量,整数之间以一 个空格隔开;

第二行输入 n 个整数(整数为 1 或 0,1 表示白色棋子,0 表示黑色棋子),

表示从左到右每颗棋子的颜色,整数之间以一个空格隔开。

Output

输出一个整数,表示最少要移除多少颗棋子,才能使剩余棋子中白色棋子的数量为 m;

如果无论如何移除棋 子,都不能使剩余棋子中白色棋子的数量为 m,则输出 -1。

Sample Input Copy

8 2
0 1 0 1 1 0 0 1

Sample Output Copy

3