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

时间:2023-01-23 09:27:14

题目连接: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+贪婪)的更多相关文章

  1. Codeforces 442C Artem and Array (看题解&rpar;

    Artem and Array 经过分析我们能发现, 如果对于一个a[ i ] <= a[ i + 1 ] && a[ i ] <= a[ i - 1 ]可以直接删掉. 最 ...

  2. codeforces 442C C&period; Artem and Array&lpar;贪心&rpar;

    题目链接: C. Artem and Array time limit per test 2 seconds memory limit per test 256 megabytes input sta ...

  3. cf442C Artem and Array

    C. Artem and Array time limit per test 2 seconds memory limit per test 256 megabytes input standard ...

  4. Codeforces Round &num;504 D&period; Array Restoration

    Codeforces Round #504 D. Array Restoration 题目描述:有一个长度为\(n\)的序列\(a\),有\(q\)次操作,第\(i\)次选择一个区间,将区间里的数全部 ...

  5. Codeforces 442C

    题目链接 C. Artem and Array time limit per test 2 seconds memory limit per test 256 megabytes input stan ...

  6. codeforces 442C C&period; Artem and Array(有深度的模拟)

    题目 感谢JLGG的指导! 思路: //把数据转换成一条折线,发现有凸有凹 //有凹点,去掉并加上两边的最小值//无凹点,直接加上前(n-2)个的和(升序)//数据太大,要64位//判断凹与否,若一边 ...

  7. Artem and Array CodeForces - 442C &lpar;贪心&rpar;

    大意: 给定序列$a$, 每次任选$a_i$删除, 得分$min(a_{i-1},a_{i+1})$(无前驱后继时不得分), 求最大得分. 若一个数$x$的两边都比$x$大直接将$x$删除, 最后剩余 ...

  8. Educational Codeforces Round 11A&period; Co-prime Array 数学

    地址:http://codeforces.com/contest/660/problem/A 题目: A. Co-prime Array time limit per test 1 second me ...

  9. CodeForces - 86D D&period; Powerful array —— 莫队算法

    题目链接:http://codeforces.com/problemset/problem/86/D D. Powerful array time limit per test 5 seconds m ...

随机推荐

  1. (2)WebAPI的增删改查

    using System; using System.Collections.Generic; using System.Linq; using System.Net; using System.Ne ...

  2. 导入excle数据将excle数据插入到数据库

    实现功能是,用户可以直接导入对应数据,或者用户下载模板,填写数据,导入模板数据.easyui实现 前台页面 { text : '日清导入', iconCls : 'icon-print', handl ...

  3. SVN下错误集锦

    SVN下错误集锦 一SVN下的文件被locked不能update和commit 最近做项目的时候,遇到这个问题,SVN下的文件被locked不能update和commit.其提示如下: 解决办法:执行 ...

  4. 运行ORB-SLAM笔记&lowbar;编译篇(一)

    1.下载代码   https://github.com/raulmur/ORB_SLAM/    (同时也可以看看作者的牛叉论文,我是打算先用代码,再回头看论文) 2.打开后如下 就好像是用一件新产品 ...

  5. ALTER TABLE SWITCH&&num;39&semi; statement failed&period; The table x&&num;39&semi; is partitioned while index &&num;39&semi;x&&num;39&semi; is not partitioned&period;

    1.L_Monitoring有这么些字段,ID,Collecttime,PlateType,PlateNO以及其他一些这段.建立这个表的时候是个非分区表,其中ID是主键,并在Collecttime,P ...

  6. odoo11 访问MSQL Server等第三发数据源

    odoo框架默认的访问时Postgres数据库,但在实际的应用场景中,不可避免的使用到其他数据库,所以有必要研究如何连接其他第三方数据库,这里分享下OCA的相关模块,具体的源代码在这里. 我将第三方的 ...

  7. vuex 入坑篇

    Vuex 是什么? Vuex 是一个专为 Vue.js 应用程序开发的状态管理模式.它采用集中式存储管理应用的所有组件的状态,并以相应的规则保证状态以一种可预测的方式发生变化. 这个状态自管理应用包含 ...

  8. 「七天自制PHP框架」应用:JSON生成器

    刚刚开始学做一个WebAPP,数据查询的一般套路是通过一张PHP页面读取数据库,获得列表后“嵌写”在PHP页面中,虽然写法上丑陋至极,但也有“快糙猛”出效果的成就感,如图. 后来想想,不对啊,难道以后 ...

  9. 图论之初,拓扑排序、前向星(通过存储边来存储图)加优先队列对拓扑的优化-----hdu1285

    确定比赛名次 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Sub ...

  10. hbase性能调优(转载)

    一.服务端调优 1.参数配置 1).hbase.regionserver.handler.count:该设置决定了处理RPC的线程数量,默认值是10,通常可以调大,比如:150,当请求内容很大(上MB ...