题目链接:
给定一个长度为 n 的数列 a1,a2,...,an, 每次可以选择一个区间 [l,r], 使下标在这个区间内的数都加一或者都减一.
求至少需要多少次操作才能使数列中的所有数都一样, 并求出在保证最少次数的前提下, 最终得到的数列可能有多少种.
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;
- }
- View Code
专注于过程, 沉浸其中. 对于终究要做的事, 要选择性的忽略这件事消耗的时间, 赶紧去做, 告别拖延.
来源: http://www.bubuko.com/infodetail-3034993.html