Codeforces 442C Artem and Array(stack+贪心)

本文主要是介绍Codeforces 442C Artem and Array(stack+贪心)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目连接：Codeforces 442C Artem and Array

题目大意：给出一个数组，每次删除一个数，删除一个数的得分为两边数的最小值，如果左右有一边不存在则算作0分。问最大得分是多少。

解题思路：首先将连续的a，b，c，a > b && c > b的情况将c掉，获得min(a,b)分，这样处理后数组变成一个递増再递减的序列，除了最大和第二大的取不到，其他数字均可以得分。

样例：4 10 2 2 8

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;
typedef long long ll;
const int N = 5 * 1e5 + 5;int n, c = -1;
ll stack[N];int main () {ll x, ans = 0;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%lld", &x);while (c > 0 && stack[c-1] >= stack[c] && stack[c] < x) {ans += min(stack[c-1], x);c--;}stack[++c] = x;}sort (stack, stack + c + 1);for (int i = 0; i <= c - 2; i++)ans += stack[i];printf("%lld\n", ans);return 0;
}

这篇关于Codeforces 442C Artem and Array(stack+贪心)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---