2027: 5480 数组隔断
Memory Limit:128 MB
Time Limit:1.000 S
Judge Style:Text Compare
Creator:
Submit:71
Solved:27
Description
给定一个长度为 n 的整数数组 a1,a2,…,an。
如果一个整数数组恰好包含相同数量的奇数元素和偶数元素,就称该数组为一个平衡数组。
给定的数组 a 恰好就是一个平衡数组。
现在,我们可以将该数组从中间截断,从而得到若干个非空子数组。
关于截断操作:
- 每次操作都需要一定成本,具体来说,将数组从 ai和 ai+1之间截断,所需成本为 |ai−ai+1|。
- 所有进行的截断操作的总成本不得超过 B。
- 所有截断得到的子数组都必须也是平衡数组。
请你计算,在满足所有要求的前提下,最多可以进行多少次截断操作。
Input
第一行包含两个整数 n,B。
第二行包含 n 个整数 a1,a2,…,an。
Output
一个整数,表示在满足所有要求的前提下,可以进行的截断操作的最多次数。
Sample Input Copy
6 4
1 2 5 10 15 20
Sample Output Copy
1