e332 - NOIP2018 Day1.1.铺设道路
題目描述
題目要求計算將一條長度為 n 的道路上每個區域的下陷深度降低到 0 所需的最少天數。道路由 n 個相鄰的區域組成，每個區域的初始下陷深度為 di。每天可以選擇一個連續區間 [L, R]，並將該區間內每個區域的下陷深度減少 1，但前提是該區間內所有區域的初始下陷深度均不為 0。
解題思路
這個問題可以使用貪心策略來解決。我們可以遍歷道路上的每個區域，如果當前區域的下陷深度大於前一個區域的下陷深度，則需要額外的一天來填充從前一個區域到當前區域的間隔。因為如果我們不這樣做，我們將不得不多次填充相同的區域。
具體來說，我們維護一個變數 t1，表示前一個區域的下陷深度。對於當前區域的下陷深度 t，如果 t > t1，則需要額外的一天來填充間隔，因此將答案 ans 增加 t - t1。然後，將 t1 更新為 t，繼續遍歷下一個區域。
複雜度分析
- 時間複雜度: O(n)
- 空間複雜度: O(1)
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <stdio.h>
inline int read(){
int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
inline void write(int x) {
int stk[9],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
int main(){
int n(read()),t,t1(0),ans(0);
while(n--){
t=read();
(t>t1)&&(ans+=t-t1);
t1=t;
}
write(ans);
}