当前位置：首页 > article >正文

lanqiaoOJ 2128：重新排序 ← 一维差分

article 2025/1/20 9:22:24

【题目来源】
https://www.lanqiao.cn/problems/2128/learning/

【题目描述】
给定一个数组 A 和一些查询 Li，Ri，求数组中第 Li 至第 Ri 个元素之和。小蓝觉得这个问题很无聊，于是他想重新排列一下数组，使得最终每个查询结果的和尽可能地大。小蓝想知道相比原数组，所有查询结果的总和最多可以增加多少？

【输入格式】
输入第一行包含一个整数 n。
第二行包含 n 个整数 A1，A2，…，An，相邻两个整数之间用一个空格分隔。
第三行包含一个整数 m 表示查询的数目。
接下来 m 行，每行包含两个整数 Li、Ri，相邻两个整数之间用一个空格分隔。

【输出格式】
输出一行包含一个整数表示答案。

【输入样例】
5
1 2 3 4 5
2
1 3
2 5

【输出样例】
4

【样例说明】
原来的和为 6+14=20，重新排列为（1, 4, 5, 2, 3）后和为 10+14=24，增加了 4。

【评测用例规模与约定】
对于 30% 的评测用例，n, m≤50；
对于 50% 的评测用例，n, m≤500；
对于 70% 的评测用例，n, m≤5000；
对于所有评测用例，1≤n, m≤10^5，1≤Ai≤10^6，1≤Li≤Ri≤10^6。

【算法分析】
● 由 https://blog.csdn.net/hnjzsyjyj/article/details/120632159 知，一维前缀和确实太简单了，很容易想到。相比于前缀和，更能考核思维的是差分，前缀和的主要应用就是差分。
一个长度为 n 的一维数组 a[1]~a[n]，其对应的一维差分数组 d[] 的定义为 d[i]=a[i]-a[i-1]。即，差分数组 d[] 是原数组 a[] 相邻元素的差。显然，根据一维差分数组 d[] 的定义，可知：
d[i]=a[i]-a[i-1]，d[i-1]=a[i-1]-a[i-2]，...，d[2]=a[2]-a[1]，d[1]=a[1]-a[0]
进而推出 a[i] = d[1] + d[2] + ... + d[i]，即 a[] 是 d[] 的前缀和，所以“差分是前缀和的逆运算”。

● 把区间 [L, R] 内每个元素 a[] 加上 v，只需要把对应的 d[] 做以下操作：
（1）把 d[L] 加上 v：d[L] += v
（2）把 d[R+1] 减去 v：d[R+1] -= v
此外，依据 a[i] = d[1] + d[2] + ... + d[i]，可得：
（1）1 ≤ i < L，前缀和 a[i] 不变；
（2）L ≤ i ≤ R，前缀和 a[i] 增加了 v；
（3）R < i ≤ N，前缀和 a[i] 不变，因为被 d[R+1] 中减去的 v 抵消了。

● 一维差分模板题：https://blog.csdn.net/hnjzsyjyj/article/details/139963345
（1）构建一维差分数组
设原数组为含有 n 个数的 a 数组（下标常从 1 开始），差分数组为 d 数组（下标常从 1 开始）。则令 d[1]=a[1]，d[i]=a[i]-a[i-1]。其中，i∈[2,n]。
（2）区间操作转端点操作：d[le]+=x，d[ri+1]-=x
利用差分处理此类“多次对区间进行加减操作”的问题，可以大大降低算法的时间复杂度。这是因为，构造差分数组后，对原数组区间 [le, ri] 的加减操作就转化为对差分数组的区间端点的操作：d[le]+=x，d[ri+1]-=x。这明显大大降低了计算量，所以算法效率会很高。注意：此处的原数组及差分数组的下标都从1开始。
（3）若已知差分数组 d[i]，则由语句 d[i]+=d[i-1] 可得到原始数组的前缀和数组。其中，i∈[1,n]。

#include <bits/stdc++.h>
using namespace std;
 
const int N=1e5+5;
int a[N]; //Primitive array
int d[N]; //Difference array
 
int main() {
    int n,m;
    cin>>n>>m;
    for(int i=1; i<=n; i++) { //i from 1
        cin>>a[i];
        d[i]=a[i]-a[i-1]; //Building a difference array
    }
 
    int le,ri,c;
    while(m--) {
        cin>>le>>ri>>c;
        d[le]+=c;
        d[ri+1]-=c;
    }
 
    for(int i=1; i<=n; i++) { //i from 1
        a[i]=d[i]+a[i-1];
        cout<<a[i]<<" ";
    }
 
    return 0;
}
 
/*
in:
6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1

out:
3 4 5 3 4 2
*/

【算法代码】

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
using namespace std;
const int maxn = 1e5+5;

LL sum[maxn], a[maxn],g[maxn];
LL n,m;
LL st, en;
LL res1,res2;

int main() {
    cin >> n;
    for(int i=1; i<=n; ++i) {
        cin >> a[i];
        sum[i] = sum[i-1]+a[i];
    }
    
    cin >> m;
    while(m--) {
        cin >> st >> en;
        res1 += sum[en] - sum[st-1];
        g[st]++;
        g[en+1]--;
    }
    
    for(int i=1; i<=n; ++i) {
        g[i] += g[i-1];
    }
    
    sort(a+1, a+1+n);
    sort(g+1, g+1+n);
    for(int i=1; i<=n; ++i) {
        res2 += g[i]*a[i];
    }
    cout << res2-res1;
    
    return 0;
}

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/144918838
https://blog.csdn.net/hnjzsyjyj/article/details/144635240
https://mp.weixin.qq.com/s?__biz=MzIzNzAzNDMzMg==&mid=2456510931&idx=1&sn=11597887eceb7e57f249875045075df8&chksm=ff510fe0c82686f625d989839210262aff7cfee955b89486d5a35184f22f3665bf9c8d443e19&scene=178&cur_album_id=3698366998120824844#rd

查看全文

http://www.kler.cn/a/510485.html