本文主要是介绍【算法刷题日志】吸氧羊的StarryCoding之旅 - 贡献法计算,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目链接:https://www.starrycoding.com/problem/3
题目描述
吸氧羊终于注册了一个StarryCoding账号!(她很开心)
但是吸氧羊忘记了它的密码,她想起你是计算机大师,于是就来请教你。
她虽然不记得密码了,但她记得一个数组,而这个密码就是这个数组中所有区间的最大值之和。
你赶快求出来吧,她太想进去玩了!
本题视频题解:https://www.bilibili.com/video/BV1Bc411v71Q
输入描述
第一行一个整数 n n n,表示数组 a a a的长度。( 1 ≤ n ≤ 2 × 1 0 5 1 \le n \le 2 \times 10^5 1≤n≤2×105)
第二行 n n n个整数表示数组 a a a中的元素。( 1 ≤ a i ≤ 1 0 8 1 \le a_i \le 10^8 1≤ai≤108)
输出描述
一行一个整数表示结果。
输入样例1
5
1 1 1 1 1
输出样例1
15
解释
一共有15个区间,每个区间的最大值都是1,它们的和是15。
题解
单调栈计算出每个位置 i i i左边及右边比 a i a_i ai小的数字的个数,然后计算每个位置的贡献即可。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 9;
ll a[N],stk[N],l[N],r[N],top;
void solve()
{int n;cin >> n;for(int i = 1;i <= n;i ++) cin >> a[i];for(int i = 1;i <= n;i ++){while(top && a[stk[top]] < a[i]) top --;l[i] = top ? stk[top] + 1 : 1;stk[++ top] = i;}top = 0;for(int i = n;i > 0;-- i){while(top && a[stk[top]] <= a[i]) top --;r[i] = top ? stk[top] - 1 : n;stk[++ top] = i;}ll ans = 0;for(int i = 1;i <= n;i ++) ans += (i - l[i] + 1) * (r[i] - i + 1) * a[i];cout << ans << '\n';
}
int main(void)
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _ = 1;while(_ --) solve();return 0;
}
这篇关于【算法刷题日志】吸氧羊的StarryCoding之旅 - 贡献法计算的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!