【題解】CSES - Increasing Array

題目連結

題目大意

給定 $n$ 個正整數的數列 $a_1, \dots, a_n$。每次操作可以選擇一個數字把他增加 $1$。問最少要進行幾次操作才能使數列非嚴格遞增 ($a_1 \leq a_2 \leq \dots \leq a_n$)。

• $1 \leq n \leq 2 \cdot 10^5$
• $1 \leq a_i \leq 10^9$

題解

由左到右進行，如果當前的數字已經大於等於前一項的話我們不用對他進行操作，否則我們要把他變得至少跟前一項一樣大，因需要對 $a_i$ 進行 $a_{i - 1} - a_i$ 次操作。最後把操作次數加起來就好了。

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	long long ans = 0;
	int last = 0;
	for(int i = 0; i < n; i++) {
		int x;
		cin >> x;
		if(x < last) {
			ans += last - x;
		} else {
			last = x;
		}
	}
	cout << ans << "\n";
	return 0;
}

如果本文對您有幫助的話幫忙點擊廣告和分享吧！

© 若無特別註明，本站文章皆由 WeakMouse's Coding Blog 原創 ，轉載引用本文前請先留言告知。本文轉載請註明文章源自 WeakMouse's Coding Blog ，作者 ，並附上原文連結： 【題解】CSES - Increasing Array