1827: STEMA-C-5 移除棋子
内存限制:128 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:0
解决:0
题目描述
有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。
输入
第一行输入两个整数n,m(1≤n,m≤10^6),分别表示初始棋子数量和目标白色棋子数量,整数之间以一个空格隔开;
第二行输入n个整数(整数为1或0,1表示白色棋子,0表示黑色棋子),表示从左到右每颗棋子的颜色,整数之间以一个空格隔开。
输出
输出一个整数,表示最少要移除多少颗棋子,才能使剩余棋子中白色棋子的数量为m;如果无论如何移除棋子,都不能使剩余棋子中白色棋子的数量为m,则输出-1。
样例输入 复制
8 2
0 1 0 1 1 0 0 1
样例输出 复制
3