网站建设制作设计营销 上海今日新闻播报

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