G.小学生的复仇
一道思维题
代码实现时,可以视作有 n−1 个底边长为 1 的矩形。
最大化每个矩形的高,即可最大化所有矩形的面积之和。
从左到右遍历,维护遍历到的数的最大值,作为矩形的高。
#include <bits/stdc++.h>
using namespace std;
#define PII pair<int, int>
#define ll long long
#define int ll
const int INF = 0x3f3f3f3f;
const int N = 1e6 + 10;
void solve() {
int n;
cin >> n;
vector<int> a(n + 10);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int ans = 0;
int maxx = 0;
for (int i = 1; i < n; i++) {
if (a[i] > a[maxx]) {
ans += (i - maxx) * a[maxx];
maxx = i;
}
}
if (maxx < n - 1)
ans += (n - 1 - maxx) * a[maxx];
cout << ans << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T = 1;
// cin >> T;
while (T--) {
solve();
}
return 0;
}