首页 > 代码库 > 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;
}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。