蓝桥杯备考冲刺必刷题(C++) | 3236 小蓝的零花钱

学习C++从娃娃抓起！记录下蓝桥杯备考比赛学习过程中的题目，记录每一个瞬间。

附上汇总贴：蓝桥杯备考冲刺必刷题（C++） | 汇总-CSDN博客

【题目描述】

小蓝和小桥正在玩一个游戏，他们有一个长度为$n$的序列，其中既有偶数也有奇数，且偶数和奇数的数量相等。

小蓝有一些零花钱，他可以用这些钱来做一个特殊的操作：他在序列中选取一个位置，然后在这个位置上将序列分成两段，要求每一段中偶数和奇数的数量都相等。小蓝想要用他的零花钱尽可能多地进行这个操作，但每次操作都需要花费代价。具体而言，每次选取的位置可以看成是对序列进行切割，切割需要花费的代价为切割两端的元素的差的绝对值。小蓝想知道，在他的预算范围内，最多能进行多少次操作。

请你帮助小蓝计算最多可以进行的操作次数。

【输入】

第一行包含两个整数$n$和$B(2\le n\le 100,1\le B\le 100)$，表示序列的长度和小蓝拥有的零花钱数。

第二行包含$n$个整数$a_1,a_2,\dots,a_n(1\le a_i\le 100)$，表示给定的序列(保证在这$n$个元素中奇数的个数等于偶数的个数)。

【输出】

输出一个整数，表示在小蓝的预算范围内，能够进行的最多操作次数。

【输入样例】

6 3
1 2 3 4 5 6

【输出样例】

2

【代码详解】

#include <bits/stdc++.h>
using namespace std;
int n, b, cnt;
int a[105], odd[105], even[105], c[105];
int main()
{
    cin >> n >> b;  // 输入n和b
    for (int i=1; i<=n; i++) {  // 输入零花钱数
        cin >> a[i];
        if (a[i]%2==1) {  // 进行奇偶判断
            odd[i]=odd[i-1]+1;
            even[i]=even[i-1];
        } else {
            odd[i]=odd[i-1];
            even[i]=even[i-1]+1;
        }
    }
    int mark=0;
    for (int i=1; i<n; i++) {  // 遍历奇偶数组
        if (odd[i]==even[i]) {  // 对于奇偶数相等的位置，则可以切割
            c[++mark] = abs(a[i]-a[i+1]);  // 计算a[i]与a[i+1]的绝对值，并记录到c数组中
        }
    }
    sort(c+1, c+mark+1);  // 对c数组按照从小到大方式排序
    int tot=0;  // 定义统计值
    for (int i=1; i<=mark; i++) {  // 遍历c数组
        if (tot+c[i]<=b) {  // 如果tot加上c[i]可以满足小于等于b
            tot+=c[i];  // 则进行累加
            cnt++;  // 切割数自增1
        } else break;  // 否则退出循环
    }
    cout << cnt << endl;  // 输出切割数
    return 0;
}

【运行结果】

6 3
1 2 3 4 5 6
2