【AcWing】100. IncDec序列

佚名 5年前 (2019-04-25) 随笔 818人围观抢沙发百度已收录

题目链接：

给定一个长度为 n的数列 a1,a2,…,an，每次可以选择一个区间 [l,r]，使下标在这个区间内的数都加一或者都减一。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

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

tips：

　　1.进行问题求解的等价转换---对a数组区间的操作等价转换为对b数组其中两个元素（端点）的操作

　　2.数据范围求和后可能爆，用 long long

　　3.变成一样的，只考虑2...n---由b数组的定义可知，b[1]=a[1]；其他b[i]=a[i]-a[i-1];

　　代码中直接用a的空间来存b了，b[i]存储记录的是a[i]比a[i-1]大的相关信息，对a[i]和a[i-1]的相对大小关系进行了建模。

　　4.差分+贪心；差分：前缀和的逆运算

　　5.对每次操作的区间进行了范围讨论[i,j]是否在[2,n];

　　6.求最小次数下的方案数最后成为一个排列组合问题

　　7.疑问：为什么不考虑最后m对应的b数组的几个位置？？

其他好的题解：

　　ref1

　　ref2

#include <iostream> #include <algorithm>

using namespace std; typedef long long LL; const int N = 100010; int a[N]; int main(){ int n; cin >> n; for (int i = 1; i <= n; i ++ ) cin >> a[i]; for(int i = n; i > 1; i --) a[i] = a[i] - a[i-1];//倒着处理--mark
 LL pos = 0, neg = 0; for (int i = 2; i <= n; i++ ) if (a[i] > 0 ) pos += a[i]; else neg-=a[i]; //求负数的绝对值之和
    cout << min(pos, neg) + abs(pos - neg) << endl; cout << abs(pos - neg) + 1 << endl; return 0; }