题解 | #小红的区间增加#
小红的区间增加
http://www.nowcoder.com/questionTerminal/d82d0710232e49a28a842fa8f59c64b9
采用差分数组，将原数组变为严格单调递增等价于该数组的差分数组除了第一项都必须是正数，基于贪心的思想，如果除了第一项的某一项不是正数，则将其变为1即可，即以这一项的下标作为区间的左端点，右端点是什么无所谓。
#include<bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n), d(n);
for(int i = 0;i < n;i++) {
cin >> a[i];
if(i == 0) {
d[i] = a[i];
}
else {
d[i] = a[i] - a[i - 1];
}
}
long long res = 0LL;
for(int i = 1;i < n;i++) {
res += max(0, 1 - d[i]);
}
cout << res << '\n';
return 0;
}
华为工作强度 804人发布
查看5道真题和解析