平数

id: zero_number

题目

问题描述

有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

输入样例

5
1 2 -4 -1 8

输出样例

11

数据范围

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

解析

分类讨论

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

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

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

ans=∣∑i=1nai∣ans = | \sum_{i=1}^{n} a_i |

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) = |\sum^{a_i < 0} a_i|

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

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

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

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

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

用数学公式表达就是如下

ans=max{∣∑ai>0ai∣,∣∑aj<0aj∣}ans = max\{ |\sum_{a_i > 0} a_i|,|\sum_{a_j < 0} a_j| \}

代码

#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;
}

练习题目

暂无题目