題目鏈接：http://codeforces.com/contest/957/problem/D

題意：有一個水池，每天的水位會上升或者下降。每天需要在水位處劃一道白線來記錄當天的水位，如果水位處有白線，則不需要再劃。然后給你一個長為n的數組m，mi表示在第i天觀察到水位上方的白線的條數（不包括當前水位）。然后現在讓你求這n天水位下方的白線的個數和。

分析：題目要你求所有天水位下方的白線的個數之和，其實我們可以知道每天水位下方的白線+每天水位下方的白線+1=當天的白線的個數，且相鄰的兩天白線的差值為0或1；于是我們可以先對水位上方的白線+1來記錄每天的白線最少有多少條a[i]，且后一天的白線比當天多0或1條。這樣需要給每天mi+1，然后a[i+1]=max(a[i],a[i+1])。然后逆著掃一遍，來確保a[i+1]-a[i]<=1；那么所有天中水位下方的白線的個數和=a[i]-m[i]-1，求和即可

AC代碼：

1 #include<bits/stdc++.h> 2 3 using namespace std; 4 5 int a[100005],b[100006]; 6 int main(){ 7 ios_base::sync_with_stdio(0); 8 cin.tie(0); 9 int n; 10 int m[100005]; 11 while(cin>>n){ 12 for(int i=1;i<=n;i++){ 13 cin>>m[i]; 14 a[i]=m[i]+1; 15 } 16 for(int i=2;i<=n;i++){ 17 a[i]=max(a[i],a[i-1]); 18 } 19 for(int i=n-1;i>=1;i--){ 20 a[i]=max(a[i],a[i+1]-1); 21 } 22 long long result=0; 23 for(int i=1;i<=n;i++){ 24 result+=(a[i]-m[i]-1); 25 } 26 cout<<result<<endl; 27 } 28 return 0; 29 } View Code

?

轉載于:https://www.cnblogs.com/ls961006/p/8660614.html

總結

以上是生活随笔為你收集整理的codeforces 957D Riverside Curio的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。