题意
输入一个含有 n(1≤n≤100000) 个非负整数的 a 数组和一个 1~n 的排列 p 数组,求每次删除 a[p[i]] 后,最大连续子段和(不能跨越被删除的)是多少?
分析
因为都是非负整数,答案一定是尽量长的区间和。
s[i] 表示 a 的前缀和,区间(l,r]的和就是s[r]-s[l]。
我们用 STL 里的 set 存区间,一开始只有(0,n]区间,删去第一个数后,就要去掉(0,n]区间,加上(0,p[1]-1]和(p[1],n]区间,类似地每次删除一个数,就要去掉包含它的区间,加上两个新区间,同时用 multiset 储存下区间和,每次输出最大的区间和,删除时也删除掉对应的区间和。
需要注意的细节:
- set 和 multiset 默认是按从小到大排序,输出最大的只要输出最后一个就可以了;
- 删除区间和时,因为 multiset 的 erase(value) 会把等于value的元素都删除,只删除一个的话,要先find,再erase;
- 存区间 make_pair(终点,起点)这样就可以按终点从小到大排序
- 包含第p个数的区间就是 lower_bound (make_pair(p,0))
- 增加完对应的区间再删去原来的区间(就是代码里的it)。
URL:http://codeforces.com/contest/722/problem/C
代码:
#include<bits/stdc++.h>
#define ll long long
#define N 100005
using namespace std;
int n;
ll s[N];
set< pair<int,int> > seg;
multiset<ll> sum;
void erase(int p){
set< pair<int,int> > ::iterator it=seg.lower_bound(make_pair(p,));
sum.erase(sum.find(s[it->first]-s[it->second])); seg.insert(make_pair(p-,it->second)),sum.insert(s[p-]-s[it->second]);
seg.insert(make_pair(it->first,p)),sum.insert(s[it->first]-s[p]);
seg.erase(it);
}
ll max(){
multiset<ll> ::reverse_iterator mit=sum.rbegin();
return *mit;
}
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++){
int a;
scanf("%d",&a);
s[i]=s[i-]+a;
}
seg.insert(make_pair(n,));
sum.insert(s[n]);
for(int i=;i<=n;i++){
int p;
scanf("%d",&p);
erase(p);
printf("%I64d\n",max());
}
}
看到一个不用set且更快的代码,大概思路是,倒过来依次放上删除的数,然后找最大连续和。
#include<bits/stdc++.h>
using namespace std;
int x[],y[],Seg[][];
long long sum[],maxm;
bool memo[];
vector<long long> ans;
int main()
{
int n,i; scanf("%d",&n);
for(i=;i<=n;i++) scanf("%d",&x[i]);
for(i=;i<=n;i++) scanf("%d",&y[i]);
for(i=;i<=n;i++)
sum[i] = x[i] + sum[i-];
for(i=n;i>;i--)
{
// y[i] == ME ( element to be built )
Seg[y[i]][] = y[i];
Seg[y[i]][] = y[i];
memo[y[i]] = ;
if(memo[y[i]-])
Seg[y[i]][] = Seg[y[i]-][];
if(memo[y[i]+])
Seg[y[i]][] = Seg[y[i]+][];
Seg[Seg[y[i]][]][] = Seg[y[i]][];
Seg[Seg[y[i]][]][] = Seg[y[i]][];
maxm = max(maxm,sum[Seg[y[i]][]] - sum[Seg[y[i]][]-]);
ans.push_back(maxm);
}
for(i=ans.size()-;i>=;i--)
printf("%I64d\n",ans[i]);
printf("0\n");
}
【Codeforces 722C】Destroying Array (数据结构、set)的更多相关文章
-
Codeforces 722C. Destroying Array
C. Destroying Array time limit per test 1 second memory limit per test 256 megabytes input standard ...
-
CodeForces - 722C Destroying Array (并查集/集合的插入和删除)
原题链接:https://vjudge.net/problem/511814/origin Description: You are given an array consisting of n no ...
-
CodeForces 722C Destroying Array (并查集)
题意:给定 n 个数,然后每次破坏一个位置的数,那么剩下的连通块的和最大是多少. 析:用并查集来做,从后往前推,一开始什么也没有,如果破坏一个,那么我们就加上一个,然后判断它左右两侧是不是存在,如果存 ...
-
[并查集+逆向思维]Codeforces Round 722C Destroying Array
Destroying Array time limit per test 1 second memory limit per test 256 megabytes input standard inp ...
-
Intel Code Challenge Elimination Round (Div.1 + Div.2, combined) C. Destroying Array -- 逆向思维
原题中需要求解的是按照它给定的操作次序,即每次删掉一个数字求删掉后每个区间段的和的最大值是多少. 正面求解需要维护新形成的区间段,以及每段和,需要一些数据结构比如 map 和 set. map< ...
-
Intel Code Challenge Elimination Round (Div.1 + Div.2, combined) C. Destroying Array 带权并查集
C. Destroying Array 题目连接: http://codeforces.com/contest/722/problem/C Description You are given an a ...
-
CF722C. Destroying Array[并查集 离线]
链接:Destroying Array C. Destroying Array time limit per test 1 second memory limit per test 256 megab ...
-
Codeforces 482B Interesting Array(线段树)
题目链接:Codeforces 482B Interesting Array 题目大意:给定一个长度为N的数组,如今有M个限制,每一个限制有l,r,q,表示从a[l]~a[r]取且后的数一定为q,问是 ...
-
Codeforces 1077C Good Array 坑 C
Codeforces 1077C Good Array https://vjudge.net/problem/CodeForces-1077C 题目: Let's call an array good ...
随机推荐
-
[c#]一个窗体调用另一个窗体的事件
StuAddForm a = new StuAddForm(); a.IfStudent(textBox1.Text.Trim()):
-
Java Socket 编程指南
Socket,又称为套接字,Socket是计算机网络通信的基本的技术之一.如今大多数基于网络的软件,如浏览器,即时通讯工具甚至是P2P下载都是基于Socket实现的.本文会介绍一下基于TCP/IP的S ...
-
序列化和持久化 merge方法和saveOrUpdate方法
merge方法和saveOrUpdate方法的区别 merge方法是把我们提供的对象转变为托管状态的对象:而saveOrUpdate则是把我们提供的对象变成一个持久化对象:说的通俗一点就是:saveO ...
-
修改linux系统时间、rtc时间以及时间同步
修改linux的系统时间用date -s [MMDDhhmm[[CC]YY][.ss]] 但是系统重启就会从新和硬件时钟同步. 要想永久修改系统时间,就需要如下命令:hwclock hwclock - ...
-
HTML的有序列表
针对HTML的有序列表,由于平常使用的不是很多,刚开始使用的时候也是有遇到一些坑,有几个小问题: 1.li的宽度不能设置为100%,这样的话就没办法看到前面的序号 2.如果设置li的颜色字体大小,前面 ...
-
自学Zabbix3.7-事件Event
配置item.trigger.都是为发送报警做准备的,什么是事件通知呢?简单的说故障发生了,zabbix会发邮件或者短信给你,告诉你服务器的一些状况. 1. 通知条件 发送通知,需要有如下步骤 定义一 ...
-
Lua和C的语法差别
没有main函数 Lua是脚本语言,没有固定入口的main函数.当lua解析器解析某个lua代码文件时,lua解析器一样一行的解析lua脚本. print("Hello lua") ...
-
Spring Cloud分布式微服务云架构
分布式.微服务.云架构 JAVA语言开发.跨平台.高性能.高可用.安全.服务化.模块化.組件化.驱动式开发模式 commonservice eurekaNetflix 云端服务发现,一个基于 REST ...
-
hog cython
pip安装cython之后,将下面代码写入hogtest2.pyx文件(我通过改文件后缀新建) import numpy as np from PIL import Image cimport num ...
-
Google Map 形状显示
添加多段线 Polyline 构造函数带有一组用于指定线的 LatLng 坐标的 PolylineOptions,以及一组用于调整多段线视觉行为的样式. Polyline 对象在地图上绘制为一系列直线 ...