[BOI2004]Sequence
题面描述
给定整数数组$a_1,a_2,a_3...a_n$,求递增数组$b_1,b_2,b_3...b_n$
使得$|a_1 - b_1| + |a_2 - b_2| + ... + |a_n - b_n|$最大
吐槽:
这道题不是人能想出来的,太神了
很有收获?$or\; not\;?$
题解:
考虑$b$数组严格递增这个条件过于苛刻,期望$b$数组不严格递增
那么,由于$b_1 < b_2 < ... < b_n$,有$b_1 - 1 \leq b_2 - 2 ... \leq b_n - n$
我们不妨考虑新的$b'_i = b_i - i$
在$b'_i$对$a'_i = a_i - i$取到最优时,$b_i$同时对$a_i$取到最优
这时,$b‘_i$就可以相等了
两个性质
1. 对于$a'_1 \leq a'_2 \leq ... \leq a'_n$,我们取$b'i = a'i$最优
2. 对于$a'_1 \geq a'_2 \geq ... \geq a'_n$,我们取$b'i$为中位数最优
并且由于$b'_i$相等,$a'_1, a'_2...a'_n$可以任意的排列
因此,我们不妨假设已经处理好了前$i - 1$个数,正要加入第$i$个数
我们假设维护出来的$b'_i$相同的并成一个区间,$b'_i$取这个区间的中位数
对于$a'_i > b'_{i - 1}$,取$b'_i = a'_i$时,相等于递增序列
否则$a'_i < b'_{i - 1}$,我们把$i$并入$b'_{i - 1}$,得到新的中位数(因为顺序任意,所以怎么合都没问题),并继续检查
那么,我们要做的事其实就是
1. 快速合并两个区间中的数
2. 确定出区间中的中位数
左偏树就是不错的选择
复杂度$O(n\log n)$
#include <cstdio>
#include <cmath>
#include <iostream>
#define sid 1000500
#define ll long long
#define ri register int
#define ls(o) t[o].ls
#define rs(o) t[o].rs
using namespace std; char RR[];
#define isdigit(u) (u >= '0' && u <= '9')
extern inline char gc() {
static char *S = RR + , *T = RR + ;
if(S == T) S = RR, fread(RR, , , stdin);
return *S ++;
}
inline int read() {
int o = , w = ; char c = gc();
while(!isdigit(c)) {if(c == '-') w = -; c = gc();}
while(isdigit(c)) o = o * + c - '', c = gc();
return o * w;
} int n, cnt;
int rt[sid], ld[sid], rd[sid], a[sid];
struct reHeap {
int ls, rs, sz, npl, key;
} t[sid]; inline void update(int o) {
t[o].sz = t[ls(o)].sz + t[rs(o)].sz + ;
t[o].npl = t[rs(o)].npl + ;
} int merge(int x, int y) {
if(!x || !y) return x + y;
if(t[x].key < t[y].key) swap(x, y);
rs(x) = merge(rs(x), y);
if(t[rs(x)].npl > t[ls(x)].npl) swap(ls(x), rs(x));
update(x); return x;
} int main() {
n = read();
for(ri i = ; i <= n; i ++) {
ld[++ cnt] = rd[cnt] = rt[cnt] = i;
a[i] = t[i].key = read() - i; t[i].sz = ;
while(cnt > && t[rt[cnt]].key < t[rt[cnt - ]].key) {
cnt --; rd[cnt] = rd[cnt + ];
rt[cnt] = merge(rt[cnt], rt[cnt + ]);
while(t[rt[cnt]].sz * > rd[cnt] - ld[cnt] + )
rt[cnt] = merge(ls(rt[cnt]), rs(rt[cnt]));
}
}
ll ans = ;
for(ri i = ; i <= cnt; i ++)
for(ri j = ld[i]; j <= rd[i]; j ++)
ans += abs(t[rt[i]].key - a[j]);
printf("%lld\n", ans);
for(ri i = ; i <= cnt; i ++)
for(ri j = ld[i]; j <= rd[i]; j ++)
printf("%d ", t[rt[i]].key + j);
return ;
}
最新文章
- Firefox开发者专版浏览器,Web开发者利器.
- 手动配置三台虚拟机pacemaker+corosync并添加httpd服务
- React的井字过三关(1)
- 我所理解的RESTful Web API [Web标准篇]
- 分享20个最新的免费 UI 设计素材给设计师
- 利用 NSSortDescriptor 对 NSMutableArray 排序
- C语言结构体的初始化
- [Oracle][ODBC SQL Server Driver][SQL Server]对象名 &#39;RECOVER.HS_TRANSACTION_LOG&#39; 无效(转)
- 24、jQuery常用AJAX-API/Java调用MySQL / Oracle过程与函数
- javascript 函数式编程
- Mybatis配置
- Nmap 源代码学习四 软件简单使用
- 用JS做图片轮播
- swift学习笔记(七)自己主动引用计数
- Javascript学习十
- 数据库复习总结(17)-T-Sql编程
- sql存储过程调用示例
- Python-HTML CSS 练习
- day0315 迭代器
- logic:equal 标签的使用(转)
热门文章
- 始终要重载toString
- 【BZOJ2683】简单题 [分治][树状数组]
- Spring: J2EE框架
- POJ 3734 Blocks (矩阵快速幂)
- NYOJ 136 等式 (哈希)
- Warning: Permanently added the RSA host key for IP address &#39;192.30.253.113&#39; to the list of known hosts. Permission denied (publickey). fatal: Could not read from remote repository. Please make sure y
- 【BubbleCup X】F:Product transformation
- scrapy shell 用法(慢慢更新...)
- 转:google测试分享-测试经理
- 【hdoj_2566】统计硬币(母函数?)