Codeforces round 493 div2 B.Cutting

There are a lot of things which could be cut — trees, paper, “the rope”. In this problem you are going to cut a sequence of integers.

There is a sequence of integers, which contains the equal number of even and odd numbers. Given a limited budget, you need to make maximum possible number of cuts such that each resulting segment will have the same number of odd and even integers.

Cuts separate a sequence to continuous (contiguous) segments. You may think about each cut as a break between two adjacent elements in a sequence. So after cutting each element belongs to exactly one segment. Say, [4,1,2,3,4,5,4,4,5,5][4,1,2,3,4,5,4,4,5,5]  two cuts →→[4,1|2,3,4,5|4,4,5,5][4,1|2,3,4,5|4,4,5,5].  On each segment the number of even elements should be equal to the number of odd elements.

The cost of the cut between xx and yy numbers is |xy|bitcoins. Find the maximum possible number of cuts that can be made while spending no more than Bbitcoins.

Input

First line of the input contains an integer n (2n1002≤n≤100) and an integer B (1B1001≤B≤100) — the number of elements in the sequence and the number of bitcoins you have.

Second line contains nn integers: a1a2 …, anan (1ai100) — elements of the sequence, which contains the equal number of even and odd numbers

Output

Print the maximum possible number of cuts which can be made while spending no more than B bitcoins.

Examples

Input
6 4
1 2 5 10 15 20
Output
1
Input
4 10
1 3 2 4
Output
0
Input
6 100
1 2 3 4 5 6
Output
2

Note

In the first sample the optimal answer is to split sequence between 22 and 55. Price of this cut is equal to 33 bitcoins.

In the second sample it is not possible to make even one cut even with unlimited number of bitcoins.

In the third sample the sequence should be cut between 22 and 33, and between 44 and 55. The total price of the cuts is 1+1=21+1=2 bitcoins.

题意:

给出一段数列,里面有N个数ai,奇数个数和偶数个数相同,然后你可以在奇数和偶数个数相等的时候,你就可以剪一个片段,需要花费|a[i]-a[i+1]|。现在总共预算是b,让你在b预算内,尽可能的多剪片段,输出最多的剪的次数。

题解:贪心  先把所有能减的片段,奇数和偶数个数相等的时候,把花费存起来,然后排个序,按照贪心原则从小的累加,在不超出预算的前提下输出累计的结果值。

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
ll jishu,oushu,ansnum,out;
ll a[120],b[120];
int main()
{
  ll n,m;//数组元素个数与比特币数量
  cin>>n>>m;
  for(int i=1;i<=n;i++)
  {
    cin>>a[i];
  }
  for(int i=1;i<=n-1;i++)
  {
    if(a[i]&1) jishu++;
    else oushu++;
    if(jishu==oushu) 
    {
      b[ansnum++]=abs(a[i+1]-a[i]);
      jishu=oushu=0;
    }
  }
  sort(b,b+ansnum);
  for(int i=0;i<ansnum;i++)
  {
    if(m>=b[i])
    {
      m-=b[i];
      out++;
    }
  }
  cout<<out<<endl;
}

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

11 + 10 =