題目鏈接：Riverside Curio

題意

ArkadyArkady 打算觀察一條河的水位 nn 天，每天他都在水平面處做一個標記，水的漲落不會將之前的標記沖走，每天他都會記錄下嚴格在水平面上方的標記數量 mimi，如果記嚴格在水平面下方的標記數為 didi，求 ∑ni=1di∑i=1ndi 的最小值。

輸入

第一行為一個整數 n?(1≤n≤105)n(1≤n≤105)，第二行為 nn 個整數 m1,m2,?,mn (0≤mi<i)m1,m2,?,mn (0≤mi<i)。

輸出

輸出最小的 ∑ni=1di∑i=1ndi 的值。

樣例

輸入

6 0 1 0 3 0 2

輸出

6

提示

最優的水平面的漲落情況如下： 注意第 33 天必須要打上 11 個新的標記，否則無法保證第 44 天在水平面上方出現 33 個標記。

輸入

5 0 1 2 1 2

輸出

1

提示

最優的水平面的漲落情況如下：

輸入

5 0 1 1 2 2

輸出

0

題解

首先找到最大的 mimi，在這一天之后不再生成新的標記，這樣可以使得在這一天之后的 ∑nj=i+1di∑j=i+1ndi 的值最小，這一天之后的 djdj 的和為 ∑nj=i+1(mi?mj)∑j=i+1n(mi?mj)，在這一天之前，只要計算出每一天最少的標記數即可，我們從第 ii 天往前枚舉 jj，設總的標記數為 totaltotal，如果在第 jj 天之前的最大值小于 totaltotal，那么第 jj 天的標記就可以認為是新畫上的，將 totaltotal 減一，繼續往前枚舉，每天在水平面下方的標記數為 total?mjtotal?mj。

過題代碼

#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <climits> #include <cstring> #include <string> #include <vector> #include <list> #include <queue> #include <stack> #include <map> #include <set> #include <bitset> #include <algorithm> #include <functional> #include <iomanip> using namespace std;#define LL long long const int maxn = 100000 + 100; int n, tot; LL ans; int num[maxn], Max[maxn];int main() {#ifdef LOCALfreopen("test.txt", "r", stdin); // freopen("test1.out", "w", stdout);#endif // LOCALios::sync_with_stdio(false);while(scanf("%d", &n) != EOF) {ans = 0;tot = 0;int Index = 1;for(int i = 1; i <= n; ++i) {scanf("%d", &num[i]);if(num[i] > num[Index]) {Index = i;}}tot = num[Index];Max[0] = 0;for(int i = 1; i <= n; ++i) {Max[i] = max(Max[i - 1], num[i]);}for(int i = Index + 1; i <= n; ++i) {ans += num[Index] - num[i];}for(int i = Index; i >= 1; --i) {ans += tot - num[i];if(Max[i - 1] < tot) {--tot;}}printf("%I64d\n", ans);}return 0; }

總結

以上是生活随笔為你收集整理的Codeforces 924C Riverside Curio（瞎搞）的全部內容，希望文章能夠幫你解決所遇到的問題。

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