蓝桥杯备赛 | 洛谷做题打卡day6
【蓝桥杯重点】还不快来学贪心算法!
小A的糖果
题目描述
小 A 有 n n n 个糖果盒,第 i i i 个盒中有 a i a_i ai 颗糖果。
小 A 每次可以从其中一盒糖果中吃掉一颗,他想知道,要让任意两个相邻的盒子中糖的个数之和都不大于 x x x,至少得吃掉几颗糖。
(ww喜欢在博客里放一些自己喜欢的图,有喜欢芽衣的举爪(≧∇≦)ノ)
输入格式
输入的第一行是两个用空格隔开的整数,代表糖果盒的个数 n n n 和给定的参数 x x x。
第二行有 n n n 个用空格隔开的整数,第 i i i 个整数代表第 i i i 盒糖的糖果个数 a i a_i ai。
输出格式
输出一行一个整数,代表最少要吃掉的糖果的数量。
样例 #1
样例输入 #1
3 3
2 2 2
样例输出 #1
1
样例 #2
样例输入 #2
6 1
1 6 1 2 0 4
样例输出 #2
11
样例 #3
样例输入 #3
5 9
3 1 4 1 5
样例输出 #3
0
提示
样例输入输出 1 解释
吃掉第 2 盒中的一个糖果即可。
样例输入输出 2 解释
第 2 盒糖吃掉 6 6 6 颗,第 4 盒吃掉 2 2 2 颗,第 6 盒吃掉 3 3 3 颗。
数据规模与约定
-
对于 30 % 30\% 30% 的数据,保证 n ≤ 20 n \leq 20 n≤20, a i , x ≤ 100 a_i, x \leq 100 ai,x≤100。
-
对于 70 % 70\% 70% 的数据,保证 n ≤ 1 0 3 n \leq 10^3 n≤103, a i , x ≤ 1 0 5 a_i, x \leq 10^5 ai,x≤105。
-
对于 100 % 100\% 100% 的数据,保证 2 ≤ n ≤ 1 0 5 2 \leq n \leq 10^5 2≤n≤105, 0 ≤ a i , x ≤ 1 0 9 0 \leq a_i, x \leq 10^9 0≤ai,x≤109。
学会利用新知,自己多试试并尝试积攒一些固定解答方案,debug,以下是我的代码 ~
#include<iostream>
#include<vector>
//vector <int> a[1001];这里想尝试用vector动态存储,但不知道为什么编译器会报错,所以暂且还是用整型定义数组吧
using namespace std;
int main()
{
long long n, x,c=0,a[100010];//由于之前用int定义在评测时会被扣分qaq,参考前辈们的代码改用long long定义了
cin >> n >> x;
for (int i = 1; i <= n; i++) cin >> a[i];//输入数组
for (int i = 1; i < n; i++)
{
if (a[i] + a[i + 1] > x)//执行循环,如果二者之和超过x,就将后面的数减去和与x的差值
{
c += a[i] + a[i + 1] - x;
a[i + 1] -= a[i] + a[i + 1] - x;
}
}
cout << c << endl;//输出c的值,华丽谢幕~
return 0;
}
我的一些话
-
关于贪心算法:尝试贪心算法后,发觉其实质上不过是模拟题的升级与优化,且其突出特点是找寻局部最优解而非全局最优解。学会利用新知,自己多试试并尝试积攒一些固定解答方案。要坚持做题哦,其实大多数人的努力,都还没有到拼天赋的程度;在一切未知之前,我们能做的便是享受当下并做自己喜欢且认为有意义的事情。
(*上面这段代码虽然已经AC了,但是由于数组长度过大受限,在附加题的处理上还有一些欠缺,有更好的处理或者优化方案的话非常欢迎前辈们提出)
-
总结来说思路很重要,多想想,多在草稿纸上画画,用测试数据多调试,debug后成功编译并运行出正确结果真的会感到很幸福!
-
关于之前蓝桥杯备赛的路线和基本方法、要掌握的知识,之前的博文我都有写,欢迎大家关注我,翻阅自取哦~文章来源:https://www.toymoban.com/news/detail-815742.html
-
不管什么都要坚持吧,三天打鱼两天晒网无法形成肌肉记忆和做题思维,该思考的时候一定不要懈怠,今天就说这么多啦,欢迎评论留言,一起成长:)文章来源地址https://www.toymoban.com/news/detail-815742.html
到了这里,关于【蓝桥杯重点】还不快来学贪心算法!的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!