IncDec Sequence

给定一个长度为 n 的数列 A1,A2,…,An，每次可以选择一个区间 [l,r]，使下标在这个区间内的数都加一或者都减一。

求至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列可能有多少种。

输入格式

第一行输入正整数 n。

接下来 n 行，每行输入一个整数，第 i+1 行的整数代表 Ai。

输出格式

第一行输出最少操作次数。

第二行输出最终能得到多少种结果。

数据范围

0  < n  ≤  10^5,
0  ≤ Ai < 2147483648

输入样例：

4
1
1
2
2

输出样例：

1
2

思路分析：

　　数组  A : 1 1 2 2

　　可化为差分数组即 ： 1 0 1 0；

　　将所有数变成相同即将 差分数组 第 2 位开的数全为 0 即可；

　　①可以将一个区间内的所有数全加一，即 Ai ++, Aj+1 --；

　　②可以将一个区间内的所有数全减一，即 Ai --  , Aj+1 ++；

　　可以将1 0 1 0 进行 ①操作  为  2 0 0 0，②操作 1 0 0 0 1  //哎 没错区间可不是非得 n 以内；

　　设

　　所以最少操作次数为 min(q, p) + | p - q | ，得到的最终序列能有 | p - q | + 1 种。// q 为 正数总和 ，p 为 负数 总和。一正一负一次操作可以抵消，剩下的必须一次一次消；

#include <bits/stdc++.h>
using namespace std;
int a[100005], n;
int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    for(int i = n; i > 0; i--){
        a[i] -= a[i - 1];
    }
    long long q = 0, p = 0;
    for(int i = 2; i <= n; i++){
        if(a[i] > 0) q += a[i];
        else         p -= a[i];
    }
    cout << min(q,p) + abs(q - p) << endl;
    cout << abs(q - p) + 1 << endl;
    
    return 0;
}

最高的牛

9 3 5 5
1 3
5 3
4 3
3 7
9 8

5
4
5
3
4
4
5
5
5

#include <bits/stdc++.h>
using namespace std;
int N, P, H, M, a[10005], x, y;
int main(){
    map<pair<int, int>, bool> book;
     cin >> N >> P >> H >> M;
     while(M--){
         cin >> x >> y;
         a[1] = H;
         if(abs(x - y) == 1)continue;
         if(book[make_pair(x, y)])continue;
         book[make_pair(x, y)] = true;
         if(x > y)swap(x, y);
         a[x + 1]--;
         a[y]++;
    }
    for (int i = 1; i <= N; i++){
        a[i] += a[i - 1];
        cout << a[i] << endl;
    }
    return 0;
}

IncDec 与 最高的牛 ---差分练习两道 题

原文：https://www.cnblogs.com/rongrongrong/p/15211869.html