题目连接: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+贪婪)的更多相关文章
-
Codeforces 442C Artem and Array (看题解)
Artem and Array 经过分析我们能发现, 如果对于一个a[ i ] <= a[ i + 1 ] && a[ i ] <= a[ i - 1 ]可以直接删掉. 最 ...
-
codeforces 442C C. Artem and Array(贪心)
题目链接: C. Artem and Array time limit per test 2 seconds memory limit per test 256 megabytes input sta ...
-
cf442C Artem and Array
C. Artem and Array time limit per test 2 seconds memory limit per test 256 megabytes input standard ...
-
Codeforces Round #504 D. Array Restoration
Codeforces Round #504 D. Array Restoration 题目描述:有一个长度为\(n\)的序列\(a\),有\(q\)次操作,第\(i\)次选择一个区间,将区间里的数全部 ...
-
Codeforces 442C
题目链接 C. Artem and Array time limit per test 2 seconds memory limit per test 256 megabytes input stan ...
-
codeforces 442C C. Artem and Array(有深度的模拟)
题目 感谢JLGG的指导! 思路: //把数据转换成一条折线,发现有凸有凹 //有凹点,去掉并加上两边的最小值//无凹点,直接加上前(n-2)个的和(升序)//数据太大,要64位//判断凹与否,若一边 ...
-
Artem and Array CodeForces - 442C (贪心)
大意: 给定序列$a$, 每次任选$a_i$删除, 得分$min(a_{i-1},a_{i+1})$(无前驱后继时不得分), 求最大得分. 若一个数$x$的两边都比$x$大直接将$x$删除, 最后剩余 ...
-
Educational Codeforces Round 11A. Co-prime Array 数学
地址:http://codeforces.com/contest/660/problem/A 题目: A. Co-prime Array time limit per test 1 second me ...
-
CodeForces - 86D D. Powerful array —— 莫队算法
题目链接:http://codeforces.com/problemset/problem/86/D D. Powerful array time limit per test 5 seconds m ...
随机推荐
-
(2)WebAPI的增删改查
using System; using System.Collections.Generic; using System.Linq; using System.Net; using System.Ne ...
-
导入excle数据将excle数据插入到数据库
实现功能是,用户可以直接导入对应数据,或者用户下载模板,填写数据,导入模板数据.easyui实现 前台页面 { text : '日清导入', iconCls : 'icon-print', handl ...
-
SVN下错误集锦
SVN下错误集锦 一SVN下的文件被locked不能update和commit 最近做项目的时候,遇到这个问题,SVN下的文件被locked不能update和commit.其提示如下: 解决办法:执行 ...
-
运行ORB-SLAM笔记_编译篇(一)
1.下载代码 https://github.com/raulmur/ORB_SLAM/ (同时也可以看看作者的牛叉论文,我是打算先用代码,再回头看论文) 2.打开后如下 就好像是用一件新产品 ...
-
ALTER TABLE SWITCH&#39; statement failed. The table x&#39; is partitioned while index &#39;x&#39; is not partitioned.
1.L_Monitoring有这么些字段,ID,Collecttime,PlateType,PlateNO以及其他一些这段.建立这个表的时候是个非分区表,其中ID是主键,并在Collecttime,P ...
-
odoo11 访问MSQL Server等第三发数据源
odoo框架默认的访问时Postgres数据库,但在实际的应用场景中,不可避免的使用到其他数据库,所以有必要研究如何连接其他第三方数据库,这里分享下OCA的相关模块,具体的源代码在这里. 我将第三方的 ...
-
vuex 入坑篇
Vuex 是什么? Vuex 是一个专为 Vue.js 应用程序开发的状态管理模式.它采用集中式存储管理应用的所有组件的状态,并以相应的规则保证状态以一种可预测的方式发生变化. 这个状态自管理应用包含 ...
-
「七天自制PHP框架」应用:JSON生成器
刚刚开始学做一个WebAPP,数据查询的一般套路是通过一张PHP页面读取数据库,获得列表后“嵌写”在PHP页面中,虽然写法上丑陋至极,但也有“快糙猛”出效果的成就感,如图. 后来想想,不对啊,难道以后 ...
-
图论之初,拓扑排序、前向星(通过存储边来存储图)加优先队列对拓扑的优化-----hdu1285
确定比赛名次 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Sub ...
-
hbase性能调优(转载)
一.服务端调优 1.参数配置 1).hbase.regionserver.handler.count:该设置决定了处理RPC的线程数量,默认值是10,通常可以调大,比如:150,当请求内容很大(上MB ...