| 题目名称 | 851. 修整数列 |
|---|---|
| 输入输出 | seq.in/out |
| 难度等级 | ★★★☆ |
| 时间限制 | 2000 ms (2 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 20 |
| 题目来源 |
 cqw
于2012-07-07加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：2， 提交：3， 通过率：66.67% | ||||
 深绘里 |
100 | 0.249 s | 3.36 MiB | C++ |
 FoolMike |
100 | 0.410 s | 2.33 MiB | C++ |
|
深绘里 |
0 | 40.000 s | 3.36 MiB | C++ |
| 本题关联比赛 | |||
| 20120707 | |||
| 关于 修整数列 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
膜拜神犇代码，榜1代码被我打上了注释。
谁能证明一下这个做法的复杂度？感激不尽。 | ||||
【题目描述】
有一个长度为n的数列c_i，我们每次可以执行一个下面的操作之一:
1.选择一个区间[l,r]，区间内每个数加上a
2.选择一个区间[l,r]，区间内每个数减去a
3.选择一个区间[l,r]，区间内每个数加上b
4.选择一个区间[l,r]，区间内每个数减去b
现在想用最少的操作次数使得数列的每个元素都变为0，请你计算出最少的操作次数
【输入格式】
第一行三个整数n，a，b，含义如题目所示
接下来一行n个整数，表示数列c_i
【输出格式】
一行一个整数，表示最少的操作次数。如果没有可行方案，直接输出-1
【样例输入】
5 2 3
1 2 1 1 -1
【样例输入】
5
【数据规模】
对于30%的数据，1 <= n,a,b <= 200, -200 <= c_i <= 200
对于60%的数据，1 <= n,a,b <= 2000, -2000 <= c_i <= 2000
对于100%的数据，1 <= n <= 100000, 1 <= a, b <= 10^9, -10^9 <= c_i <= 10^9
【时限】
2s