【鏈接】 我是鏈接,點(diǎn)我呀:)
【題意】

題意

【題解】

設(shè)第i天總共的線數(shù)為t[i]
水平線上線數(shù)為m[i]是固定的
水平線下的線數(shù)設(shè)為d[i]
則d[i]+m[i]+1=t[i]
也就是說(shuō)問(wèn)題可以轉(zhuǎn)化為使得t[i]最小
我們可以列出關(guān)于t[i]的不等式
t[i]= max{t[i-1],m[i]+1} ···①
t[i]+1>=t[i+1] ,因?yàn)槊刻熳疃鄤澮粭l線 ····②
對(duì)于①式,直接順推就好
對(duì)于②式
我們用t[i]>=t[i+1]-1逆推
只要t[i]<t[i+1]-1那么就把t[i]擴(kuò)大為t[i+1]-1
因?yàn)閠[i]每次推的時(shí)候都在擴(kuò)大,而且小于t[i+1]所以,①式的性質(zhì)不會(huì)被破壞。
同時(shí)也能夠使得每個(gè)t[i]的值都為最小的t[i+1]-1.

【代碼】

#include <bits/stdc++.h> using namespace std; const int N = 1e5;int n; int m[N+10],t[N+10],d[N+10];int main(){ios::sync_with_stdio(0),cin.tie(0);cin >> n;for (int i = 1;i <= n;i++) cin >> m[i];for (int i = 1;i <= n;i++){t[i] = max(t[i-1],m[i]+1);}for (int i = n-1;i >= 1;i--){//t[i]+1>=t[i+1]//t[i]>=t[i+1]-1if (t[i]<t[i+1]-1){t[i] = t[i+1]-1;}}for (int i = 1;i <= n;i++){d[i] = t[i]-m[i]-1;}long long ans = 0;for (int i = 1;i <= n;i++){ans = ans + d[i];}cout<<ans<<endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的【Codeforces 924C】Riverside Curio的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。