P4552 [Poetize6] IncDec Sequence

2020 年 10 月 8 日
筆記
差分

Link

題目描述

給定一個長度為 \(n\) 的數列 \({a_1,a_2,\cdots,a_n}\)，每次可以選擇一個區間 \([l,r]\)，使這個區間內的數都加 \(1\) 或者都減 \(1\)。

請問至少需要多少次操作才能使數列中的所有數都一樣，並求出在保證最少次數的前提下，最終得到的數列有多少種。

輸入格式

第一行一個正整數 \(n\)
接下來 \(n\) 行,每行一個整數,第 \(i+1\) 行的整數表示 \(a_i\)。

輸出格式

第一行輸出最少操作次數
第二行輸出最終能得到多少種結果

輸入輸出樣例

輸入 #1

輸出 #1

1
2

說明/提示

對於 100% 的數據，\(1n\le 100000, 0 \le a_i \le 2^{31}\)。

差分的水題。

首先對於第一問的話，我們可以對原序列差分一下，然後我們兩種區間操作就變成了，一個值加一，一個值減一。

我們要讓操作次數儘可能的小，所以每次要盡量的把一個正數和負數湊在一起進行操作。

設所有差分數組正數的和 \(a\),負數的和為 \(b\),那麼我們的最小操作次數就是 \(max(-a,b)\)

對於第二問的話，我們進行了 \(min(-a,b)\) 次操作之後，肯定只會剩下一個負數或者正數 \(x\)，剩下的數就全為零。

我們剩下的幾次操作就只能對 \(a_1,x\) 或者 \(x,a_{n+1}\) 進行操作。

然後對 \(a_1\) 進行 \(0,1,2,3,4...x\) 操作所得到的答案也是不同，所以第二問的答案為 \(abs(-a-b)+1\)

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define int long long
int n,sum1,sum2,ans;
int a[100010],d[100010];
inline int read()
{
	int s = 0,w = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0'; ch = getchar();}
	return s * w;
}
signed main()
{
	n = read();
	for(int i = 1; i <= n; i++) a[i] = read();
	for(int i = 1; i <= n; i++)
	{
		d[i] = a[i] - a[i-1];
	}
	for(int i = 2; i <= n; i++)
	{
		if(d[i] < 0) sum1 += d[i];
		if(d[i] > 0) sum2 += d[i];
	}
	ans = max(abs(sum1),sum2);
	printf("%lld\n",ans);
	printf("%lld\n",abs(-sum1-sum2)+1);
	return 0;
}

Tags: 差分