平数

1 题目

1.1 问题描述

有 $n$ 个数,$a_1,a_2,a_3,\cdots,a_n$,现在有以下操作

1. 选取任意一个数 $a_i$,加上或减去 $1$
2. 选取任意两个数 $a_i,a_j\ (i \neq j)$,其中一个加 $1$,另一个减 $1$

问题,最少操作多少次

1. 所有的数变成 $0$
2. 除了第一个数外,其它所有的数变成 $0$

2 输入样例

1
2

5
1 2 -4 -1 8

3 输出样例

1

11

4 数据范围

$n \le 10^5$,$|a_i| \le 10^5$

5 解析

分类讨论

1. 所有的数都是正数或负数

当所有的数都是正数时,显然只能挑一个数进行减 $1$,同理,都是负数时,只能挑一个数加 $1$

那最少的操作次数显然是:所有数的和的绝对值,用数学公式表示如下

2. 数有正有负

为了思考🤔复杂的问题,我们可以使用这种方法: 先简化问题的复杂度,例如缩小数量,使数据有序等,先考虑简单的问题,然后依次增加难度来寻找问题的规律, 这种方法我称为**++简化法++**

先考虑只有两数,一正一负的情况,例如 $10,-8$,答案显然是 $10$,所以这种情况下:答案是正负数绝对值的最大值

然后考虑有三个数,例如 $10,-8,-5$,答案显然是 $|-8+(-5)|=13$,所以这种情况下:答案是正负数和绝对值的最大值

我们发现:

• 只有正(负)数的时候,只用操作正(负)数,简单,答案只有正(负)数的数值与关.
• 当同时有正负数的时候,可以选一对正负数,同时操作,正减 $1$,负加 $1$.也就是说这种操作可以一值做直到只有正(负)时.
• 正数只能加 $1$,负数只能减 $1$

最后,可以想到,一般的情况下,有正有负.可以先固定一个正数不变,也就是每一次 $-1$ 都先操作在这个正数上面,加 $1$ 操作选其它的负数来进行配对操作,如果这个正数变成 $0$,那就继续找一个正数继续这样操作.

我们把问题转化成一个新问题(化归法): 设,面对一个数字集合 $A$,所有正数操作的次数为 $P(A)$,所有的负数的操作次数(也就是加了多少次,负数只能加)为 $N(A)$

显然 $P(A)=\sum_{a_i>0}a_i$ 显然 $N(A)=\left|\sum_{a_i<0}a_i\right|$

其实这种思想我称为:分解子问题.后面会重点讲这种思想

整个问题,可以形象化地等效成

• 每一个正数都对应一个红色的柱子,负数对应蓝色的柱子.
• 正数的加 $1$,就等效成红色柱子消去一层.负数同理.
• 把正数的数和负数对就的柱子磊起来,各磊成两个柱子,每一次的操作,就是同时消去两个柱子的一层,问最多操作多少次.

上面这种方法,我称为**++等效法++**,这是一种非常重要的思想.

显然最终答案为 $\max\{P(A),N(A)\}$

用数学公式表达就是如下

6 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;

int n;

int sp,sn; //正数与负数的和

int main() {

    cin >> n;
    for(int i = 1;i <= n ;++i) // i: 1->n
    {
        int t;
        std::cin >> t;
        if( t > 0)
            sp += t;
        else
            sn += -t;
    }

    cout<< max(sp,sn);

    return 0;
}

7 练习题目

• luogu P4552: [Poetize6] IncDec Sequence (洛谷 P4552)
• luogu P1969: [NOIP 2013 提高组] 积木大赛
• 最小操作次数使数字一样大

8 相关题解

暂无相关题解