【蓝桥杯重点】还不快来学贪心算法！

蓝桥杯备赛 | 洛谷做题打卡day6

【蓝桥杯重点】还不快来学贪心算法！

文章目录

• 蓝桥杯备赛 | 洛谷做题打卡day6
• 小A的糖果
• • 题目描述
  • 输入格式
  • 输出格式
  • 样例 #1
  • • 样例输入 #1
    • 样例输出 #1
  • 样例 #2
  • • 样例输入 #2
    • 样例输出 #2
  • 样例 #3
  • • 样例输入 #3
    • 样例输出 #3
  • 提示
  • • • 样例输入输出 1 解释
      • 样例输入输出 2 解释
      • 数据规模与约定
  • 我的一些话

小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
#include
//vector  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 > 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后成功编译并运行出正确结果真的会感到很幸福！

• 关于之前蓝桥杯备赛的路线和基本方法、要掌握的知识，之前的博文我都有写，欢迎大家关注我，翻阅自取哦~

• 不管什么都要坚持吧，三天打鱼两天晒网无法形成肌肉记忆和做题思维，该思考的时候一定不要懈怠，今天就说这么多啦，欢迎评论留言，一起成长：）