加加减减

题目大意

image-20220824004341018

分析

引入 [NOIP2013]积木大赛 即可选择一个区间 [l,r][l,r]，使区间内都减 11 问最少操作几次，数组变为全 00

考虑差分 d[i]=a[i]−a[i−1],i∈[1,n+1]d[i] = a[i] - a[i-1], i ∈ [1,n+1] ,对区间 [l,r][l,r] 减去 11 的操作，对于差分数组 即 d[l]−−,d[r+1]++d[l]--, d[r+1]++

那么最小操作次数就是差分数组的正数之和,并且正数之和 = | 负数之和 |

对于本题令最后数列变为 xx

那么等价于对数列 ai−xa_i - x , 通过对区间 [l,r][l,r] 加 11 或 减 11 ,使 数列 变为全 00

仍考虑差分数组 d[i]=a[i]−a[i−1],i∈[1,n+1]d[i] = a[i] - a[i-1], i ∈ [1,n+1]

d[i],i∈[2,n]d[i], i ∈[2,n] 的值不会受 xx 变化

由引入问题可知，最少的操作次数 res=(min{∣a1−x∣+∣x−an∣}+∑i=2nabs(d[i])) / 2res = (min\{|a_1-x| + |x - a_n|\} + \sum_{i=2}^{n}abs(d[i])) \ / \ 2

显然 min{∣a1−x∣+∣x−an∣}=∣a1−an∣min\{|a_1-x| + |x - a_n|\} = |a_1-a_n|

则 res=(∣a1−an∣+∑i=2nabs(d[i])) / 2res = ( |a_1-a_n| + \sum_{i=2}^{n}abs(d[i])) \ / \ 2

那么考虑 $ x $ 的取值,显然 xx 可以取 a1a_1 和 ana_n 之间的所有值

故种类数 ans=∣a1−an∣+1ans = |a_1 - a_n| + 1

Code

1
2
3
4
5
6
7
8
9
10
11
12
signed main()
{
    int n;cin>>n;
    vector<int> a(n+2),d(n+2);
    for(int i = 1;i <= n;i++) cin >> a[i];
    for(int i = 1;i <= n+1;i++) d[i] = a[i] - a[i-1];
    int res = abs(a[1]-a[n]);
    for(int i = 2;i <= n;i++) res += abs(d[i]);
    res /= 2;
    cout << res << endl << abs(a[1]-a[n])+1 << endl;
    return 0;
}