1768: STEMA-P-5 最少移除棋子数量

内存限制:128 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:0 解决:0

题目描述

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

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

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

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

例 1:

n=8,m=2;8颗棋子的颜色分别是01011001,要使剩余的棋子中白色棋子数量为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,则输出 -1

输入

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

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

输出

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

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

样例输入 复制

8 2
0 1 0 1 1 0 0 1

样例输出 复制

3

提示

贪心算法 2025年3月 05

来源/分类