蓝桥杯-符号变反操作（差分）

https://www.lanqiao.cn/problems/3910/learning

问题描述

有 n 个整数，可能为正数、0或负数。有 m 次操作，每次操作处理一个区间 [Li​,Ri​]，使得第 Li​个  第 Ri​ 个数每个数的符号变反，对 0 而言，符号变反后还是 0。数的序号从 1 开始计起。

现在允许任意调整这 nn 个数的顺序。问如何调整数的顺序后，使得 m 次操作后这 n 个数之和达到最大，以及如何调整数的顺序后，使得 m 次操作后这 n 个数之和达到最小。

输入格式

输入数据第一行为两个整数 n 和 m，1≤n,m≤105，分别表示数的个数和操作的次数。

第二行为 n 个整数，这 n 个整数均不超过 int 型范围。

接下来有 m 行，每行为两个正整数 Li​,Ri​，1≤Li​≤Ri​≤n，表示一次操作的区间。

输出格式

输出两个整数，表示调整 n 个整数的顺序，执行 m 次操作后，n 个数之和的最大值和最小值，用空格隔开。

样例输入

5 2
-9 20 -27 13 129
1 3
2 5

样例输出

172 -198

思路：差分数组记录所有区间操作的权值，然后前缀和还原数组，如果数组是奇数说明要反转，偶数就不反转，然后贪心排序a数组从小到大，如果求最大的数，每次都反转最小的数，不反转最大的数，求最小值则相反。

1. 对原数组进行排序：

   • 使用 sort 函数对数组 a 进行从小到大的排序，排序范围是 a[1] 到 a[n]。这是因为后续要根据贪心策略，选择最小或最大的数进行符号变反操作，所以先对数组进行排序，方便后续处理。

2. 利用差分数组记录区间操作：

   • 对于每一次操作，读取操作区间的左右端点 l 和 r（1≤l≤r≤n）。
   • 根据差分数组的性质，在差分数组 dif 的 l 位置增加 1（表示从 l 位置开始有一次符号变反操作），在 r + 1 位置减少 1（表示 r 位置结束后不再有这次符号变反操作）。这样通过遍历 dif 数组并进行前缀和计算，就可以得到每个位置实际受到的符号变反操作的次数。

3. 计算前缀和并根据操作次数处理数组元素：

   • 遍历差分数组 dif，计算其前缀和，即 dif[i] += dif[i - 1]。此时 dif[i] 表示位置 i 总共受到的符号变反操作的次数。
   • 定义变量 ans1 和 ans2 分别用于记录操作后 n 个数之和的最大值和最小值，同时定义四个指针 max_l、max_r、min_l、min_r 分别用于指向排序后数组 a 的头和尾，用于贪心选择合适的数。
   • 再次遍历 dif 数组，对于每个位置 i：
     • 如果 dif[i] 为奇数，说明位置 i 上的数需要进行符号变反操作。为了使和最大，我们选择最小的数进行变反，即 ans1 -= a[max_l++]；为了使和最小，我们选择最大的数进行变反，即 ans2 -= a[min_r--]。
     • 如果 dif[i] 为偶数，说明位置 i 上的数不需要进行符号变反操作。为了使和最大，我们选择最大的数，即 ans1 += a[max_r--]；为了使和最小，我们选择最小的数，即 ans2 += a[min_l++]。

代码：

#include <iostream>
#include <algorithm>
using namespace std;

int n,m,a[100005],dif[100005];

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=m;++i){
        int l,r;
        cin>>l>>r;
        dif[l]++;dif[r+1]--;
    }
    int ans1=0,ans2=0,max_l=1,max_r=n,min_l=1,min_r=n;
    for(int i=1;i<=n;++i){
        dif[i]+=dif[i-1];
        if(dif[i]%2){
            ans1-=a[max_l++];
            ans2-=a[min_r--];
        }
        else{
            ans1+=a[max_r--];
            ans2+=a[min_l++];
        }
    }
    cout<<ans1<<" "<<ans2;
    return 0;
}