藍(lán)橋杯備賽 | 洛谷做題打卡day6
【藍(lán)橋杯重點】還不快來學(xué)貪心算法！
小A的糖果
題目描述
小 A 有 n n n 個糖果盒，第 i i i 個盒中有 a i a_i ai? 顆糖果。
小 A 每次可以從其中一盒糖果中吃掉一顆，他想知道，要讓任意兩個相鄰的盒子中糖的個數(shù)之和都不大于 x x x，至少得吃掉幾顆糖。
（ww喜歡在博客里放一些自己喜歡的圖，有喜歡芽衣的舉爪(≧?≦)?）
輸入格式
輸入的第一行是兩個用空格隔開的整數(shù)，代表糖果盒的個數(shù) n n n 和給定的參數(shù) x x x。
第二行有 n n n 個用空格隔開的整數(shù)，第 i i i 個整數(shù)代表第 i i i 盒糖的糖果個數(shù) a i a_i ai?。
輸出格式
輸出一行一個整數(shù)，代表最少要吃掉的糖果的數(shù)量。
樣例 #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 顆。
數(shù)據(jù)規(guī)模與約定
-
對于 30 % 30\% 30% 的數(shù)據(jù)，保證 n ≤ 20 n \leq 20 n≤20， a i , x ≤ 100 a_i, x \leq 100 ai?,x≤100。
-
對于 70 % 70\% 70% 的數(shù)據(jù)，保證 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% 的數(shù)據(jù)，保證 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。
學(xué)會利用新知，自己多試試并嘗試積攢一些固定解答方案，debug，以下是我的代碼 ~
#include<iostream>
#include<vector>
//vector <int> a[1001];這里想嘗試用vector動態(tài)存儲，但不知道為什么編譯器會報錯，所以暫且還是用整型定義數(shù)組吧
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];//輸入數(shù)組
for (int i = 1; i < n; i++)
{
if (a[i] + a[i + 1] > x)//執(zhí)行循環(huán)，如果二者之和超過x，就將后面的數(shù)減去和與x的差值
{
c += a[i] + a[i + 1] - x;
a[i + 1] -= a[i] + a[i + 1] - x;
}
}
cout << c << endl;//輸出c的值，華麗謝幕~
return 0;
}
我的一些話
-
關(guān)于貪心算法：嘗試貪心算法后，發(fā)覺其實質(zhì)上不過是模擬題的升級與優(yōu)化，且其突出特點是找尋局部最優(yōu)解而非全局最優(yōu)解。學(xué)會利用新知，自己多試試并嘗試積攢一些固定解答方案。要堅持做題哦，其實大多數(shù)人的努力，都還沒有到拼天賦的程度；在一切未知之前，我們能做的便是享受當(dāng)下并做自己喜歡且認(rèn)為有意義的事情。
（*上面這段代碼雖然已經(jīng)AC了，但是由于數(shù)組長度過大受限，在附加題的處理上還有一些欠缺，有更好的處理或者優(yōu)化方案的話非常歡迎前輩們提出）
-
總結(jié)來說思路很重要，多想想，多在草稿紙上畫畫，用測試數(shù)據(jù)多調(diào)試，debug后成功編譯并運行出正確結(jié)果真的會感到很幸福！
-
關(guān)于之前藍(lán)橋杯備賽的路線和基本方法、要掌握的知識，之前的博文我都有寫，歡迎大家關(guān)注我，翻閱自取哦~文章來源：http://www.zghlxwxcb.cn/news/detail-815742.html
-
不管什么都要堅持吧，三天打魚兩天曬網(wǎng)無法形成肌肉記憶和做題思維，該思考的時候一定不要懈怠，今天就說這么多啦，歡迎評論留言，一起成長：）文章來源地址http://www.zghlxwxcb.cn/news/detail-815742.html
到了這里，關(guān)于【藍(lán)橋杯重點】還不快來學(xué)貪心算法！的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
