【第002题】题解分享：P4552 [Poetize6] IncDec Sequence

小码匠

发布于 2023-10-31 10:45:56

30800

代码可运行

文章被收录于专栏：小码匠和老码农小码匠和老码农

运行总次数：0

代码可运行

大家好！我是小码匠。

今天分享的题目是标准的差分题目。

路漫漫其修远兮，吾将上下而求索

离自己的既定目标：

目标：300道
已完成：4道
待完成：296道

10/23～10/24

本周完成4道，后面2道稍后会进行分享

分类	算法	题目
算法基础	前缀和	【第001题】题解分享：湖南省选->激光炸弹
算法基础	差分	【第002题】题解分享：P4552 [Poetize6] IncDec Sequence

前置知识

差分

题目地址

https://www.luogu.com.cn/problem/P4552

题目描述

给定一个长度为 n 的数列

a_1,a_2,⋯,a_n

，每次可以选择一个区间[l,r]，使这个区间内的数都加 1 或者都减 1。

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

输入格式

第一行一个正整数 n 接下来 n 行,每行一个整数,第 i+1行的整数表示

a_i

。

输出格式

第一行输出最少操作次数第二行输出最终能得到多少种结果

输入输出样例

输入 #1复制

输出 #1复制

1
2

说明/提示

对于 100% 的数据，

n≤100000,0≤a_i≤2^{31}

。

题解

思路

思路可参照：https://www.luogu.com.cn/problem/solution/P4552

AC代码

#include <bits/stdc++.h>

using namespace std;

void best_coder() {
    int n;
    cin >> n;
    vector<long long> a(n + 1);
    cin >> a[0];
    long long z = 0, f = 0;
    for (int i = 1; i < n; ++i) {
        cin >> a[i];
        long long x = a[i] - a[i - 1];
        if (x > 0) {
            z += x;
        } else {
            f += x;
        }
    }
    f = abs(f);
    cout << max(z, f) << '\n';
    cout << max(z, f) - min(z, f) + 1;
}

void happy_coder() {

}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    return 0;
}