题目连接: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 Round #620 (Div. 2) [codeforces 1304A] Two Rabbits 整除+模 总目录详见https://blog.csdn.net/mrcrack/article/details/103564004 在线测评地址https://codeforces.ml/contest/1304/problem/A ...
暴枚最长桌脚的长度$l$,然后长度比$l$长的桌脚全部都要砍掉长度比$l$短的桌脚选择代价前$k$小的砍掉用线段树维护;示例程序 :typedef long l
解决问题(문제해결) ACM-ICPC凭证,BOJ,CodeForces,Codewars,SCPC,摇动,TopCoder凭证
题目大意:给出一个数列 a ,求出 题目分析:如果暴力的话显然时间复杂度是 n * n 的,我们应该想办法去优化,比赛的时候想用线段树,但是不会在维护异或的前提下区间加法,也想过用矩阵维护,但丝毫没什么用呀,...
Codeforces - 1131C. Birthday(贪心)题目链接题目给你n和n个数,要你重新排列n个数,使得这些数的相邻差值中最大的那个值最小。stat
Eugene and an array 题意: 求出一个数列中子区间满足 此区间的任意子区间之和 不为0的区间个数。 思路: 考虑用dp[x]dp[x]dp[x]记录前缀和为xxx的区间右端点。 那么这道题其实可以看成用map记录前缀和的路径,依次...
Codeforces 题库 101-200 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
贪心正确性显然:R大的至少可以选则R做为点来用。所以按R升序遍历,每次优先选左边的,能让后边的可选的更多。 用set维护可选的数即可。 这题加了个输出2个方案。 我们考虑最简单的情况:即确定一个序列后,是否有2...
codeForces C ++中的Code Force解决方案
Codeforces 题库 001-100 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
codeforces编程网站预测分数插件
Codeforces 1105B - Zuhair and Strings 测试点37个(全)
Array Shrinking time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output You are given an array a1,a2,…,an. You can perform the following operation ...
使用于Google Chrome的Codeforces Enhancer 1.1.2插件安装包。 版本:codeforces enhancer 1.1.2 使用浏览器:Google Chrome
Codeforces - 1107B. Digital root & 1107C. Brutality(规律 & 贪心)Codeforces - 1107B.
Codeforces 185A - Plant 全测试点49个
题目大意:给出 n 个数字组成的序列,现在可以对数列进行多次操作,每次操作可以选择其中一段连续的数列,用其平均数替换原位置,换句话说,若原连续数列为 1 2 3,则可以替换为 2 2 2,问如何操作可以使得最后答案...
编码 C ++中的Codeforce问题的解决方案
codeforces每日一题。 题意: 给出一个数组,让你挑选出能组成任意pair差值为2的幂的序列,并且使这个序列长度尽可能大。 思路: 针对于挑选出来的序列,任意pair对的差值为2的幂数。 假设有多个pair对,设dis(a,b)=2...