P3817 小A的糖果（贪心，模拟）
2023-01-28 17:43:55 来源：哔哩哔哩
题目：
题目描述
(相关资料图)
小 A 有 n 个糖果盒，第 i 个盒中有 ai 颗糖果。
小 A 每次可以从其中一盒糖果中吃掉一颗，他想知道，要让任意两个相邻的盒子中糖的个数之和都不大于 x，至少得吃掉几颗糖。
输入格式
输入的第一行是两个用空格隔开的整数，代表糖果盒的个数 n 和给定的参数 x。
第二行有 n 个用空格隔开的整数，第 i 个整数代表第 i 盒糖的糖果个数 ai。
输出格式
输出一行一个整数，代表最少要吃掉的糖果的数量。
输入输出样例
输入
3 32 2 2
输出
1
输入
6 11 6 1 2 0 4
输出
11
输入
5 93 1 4 1 5
输出
0
说明/提示
样例输入输出 1 解释
吃掉第 2 盒中的一个糖果即可。
样例输入输出 2 解释
第 2 盒糖吃掉 66 颗，第 4 盒吃掉 22 颗，第 6 盒吃掉 33 颗。
数据规模与约定
对于 30%30% 的数据，保证 n≤20，ai,x≤100。
对于 70%70% 的数据，保证 n≤103，ai,x≤105。
对于 100%100% 的数据，保证 2≤n≤105，ai,x≤109。
简单理解：
有n个数，每两个数之间不能超过x，求最少要减去多少才能满足前面的规定；
思路：
这题的知识点涉及到了模拟和贪心
一组一组的来判断是否大于x(一组就是第一个和第二个，第二个和第三个……),如果大于那么就要减糖果，现在就要想是要减第一个还是第二个呢？如果减一组中的第一个就不是最优解，因为减第二个是能同时减少两组的数量的，就第一组和第二组来说，第一个数是只被第一组包含的，二第二个数被一二两组同时包含，以此类推，所以减去第二个数是更优的选择
易错点：
1. 不要循环慢慢的减（“--box[i]”这样）会超时，第一次就是这样错的，要用算出来的公式
2. 要把计数变量写在减糖果操作的前面，减糖果的操作会改变box的值
前排说明一下公式（其实很简单）：
（1）box[i]+box[i+1]-x 就是这一组糖果超过x的数量
（2）box[i+1]=x-box[i] 是: box[i+1] = box[i+1] - (box[i] + box[i+1] - x ) 的简化
（3）box[i]=x 是：box[i] = box[i] - [ (box[i] + box[i+1] - x) - box[i+1]] 的简化
代码：
#include <iostream>
using namespace std;
int box[100000],cnt;
int main()
{
int n,x;
cin>>n>>x;
for(int i=0;i<n;i++)cin>>box[i];/*输入*/
for(int i=0;i<n-1;i++){
if(box[i]+box[i+1]>x&&box[i]+box[i+1]-x<=box[i+1]){//判断是否两个盒子的糖果加起来超过了x，还判断了超过的数量是否大于第二个盒子的数量
/*这里是超过数量没有超过第二个盒子的数量*/
cnt+=box[i]+box[i+1]-x;（1）
box[i+1]=x-box[i];（2）
}else if(box[i]+box[i+1]>x&&box[i]+box[i+1]-x>box[i+1]){
/*这里是超过数量超过了第二个盒子的数量*/
cnt+=box[i]+box[i+1]-x;
box[i]=x;（3）
box[i+1]=0;
}
}
cout<<cnt;
}
上一篇 : 全球资讯：覆盖课后服务 新添生境花园
下一篇 : 最后一页