洛谷 P4552 [Poetize6] IncDec Sequence C语言
P4552 [Poetize6] IncDec Sequence - 洛谷 | 计算机科学教育新生态
题目描述
给定一个长度为 n 的数列 a1,a2,…,an，每次可以选择一个区间 [l,r]，使这个区间内的数都加 1 或者都减 1。
请问至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列有多少种。
输入格式
- 第一行一个正整数 n
- 接下来 n 行，每行一个整数，第 i+1 行的整数表示 ai
输出格式
- 第一行输出最少操作次数
- 第二行输出最终能得到多少种结果
输入输出样例
输入 #1
4
1
1
2
2输出 #1
1
2说明/提示
对于 100% 的数据，n≤100000，0≤ai≤2的31次方。
思路：
代码如下：
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll N = 1e5+10;
ll arr[N];
ll pre[N];
ll n;
ll p,ne;
int main()
{cin >> n;for(ll i = 1 ; i <= n ; i++){cin >> arr[i];pre[i] = arr[i] - arr[i-1];}for(ll i = 2 ; i <= n ; i++){if(pre[i] > 0)p += pre[i];else if(pre[i] < 0)ne -= pre[i];}cout << max(p,ne) << endl;cout << max(p,ne) - min(p,ne) + 1;return 0;
}