首页 > 代码库 > bzoj3043 IncDec Sequence
bzoj3043 IncDec Sequence
传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3043
【题解】
比较神奇的一道题,开始没往差分的角度上想,所以没想出来。
考虑查分数组,有$n-1$个数,那么操作变成一个地方+1,一个地方-1.
显然最后是要让差分数组全部变成0. 设差分后所有正数的和为$cnt_a$,负数的绝对值和为$cnt_b$。
为了方便说明,我们在数组前和数组后分别增加一个虚拟差分位置。这两个位置的数是可以是任意的。
那么如果$cnt_a \not= cnt_b$,那么多出来的部分有2种选择:①跟数组前的虚拟差分位置进行操作;②跟数组后的虚拟差分位置进行操作。
由于最后剩下的一定是同一种符号的(要么正、要么负),所以只需要枚举前/后进行了多少次就行了,所以总方案是$|cnt_a - cnt_b| + 1$。
# include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int M = 5e5 + 10; const int mod = 1e9+7; # define abs(x) ((x) > 0 ? (x) : -(x)) int n, a[M]; ll cnta, cntb; int main() { cin >> n; for (int i=1; i<=n; ++i) scanf("%d", a+i); for (int i=1; i<n; ++i) a[i] = a[i+1] - a[i]; for (int i=1; i<n; ++i) if(a[i] >= 0) cnta += a[i]; else cntb -= a[i]; cout << max(cnta, cntb) << endl << abs(cnta - cntb) + 1 << endl; return 0; }
bzoj3043 IncDec Sequence
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。