第十三届蓝桥杯C++C组省赛H题—— 重新排序（AC）

1.重新排序

1.题目描述

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

2.输入格式

输入第一行包含一个整数 $n$ 。

第二行包含 $n$ 个整数 $A_1,A_2,\cdots ,A_n$ , 相邻两个整数之间用一个空格分隔。
第三行包含一个整数 $m$ 表示查询的数目。

接下来 $m$ 行, 每行包含两个整数 $L_i、R_i$, 相邻两个整数之间用一个空格分隔。

3.输出格式

输出一行包含一个整数表示答案。

4.样例输入

5
1 2 3 4 5
2
1 3
2 5

5.样例输出

4

6.样例说明

原来的和为 $6+14=20$, 重新排列为 $(1,4,5,2,3)$ 后和为 $10+14=24$, 增加了4。

7.数据范围

$1\le n,m\le 10^5,1\le Ai\le 10^6,1\le Li\le Ri\le 10^6$ 。

8.原题链接

重新排序

2.解题思路

一道Codeforces上的原题，只不过原题没有问和增加多少，贪心的思路也比较好想，不知道为什么会是 $H$ 题。查询最多能增加多少的和，其实就是用重排以后的查询和减去未重排的查询总和，未重排的查询总和是不变的，所以我们只需要最大化使得重排之后的查询总和最大。

只有处在查询区间数，值才会加到我们的计算当中，明显查询的区间有可能会重合，也就是说会存在某个位置的数多次处在查询区间中作为答案被统计，为了使得总和最大化，我们自然贪心地将值更大的数放在这些位置。

先统计出每个位置被统计的频率，也就是当查询区间为$[l,r]$时，这个区间的值全部加1，代表被统计一次，这个操作我们可以使用差分实现。在统计出未排序原数组的和res，我们将原数组排序，然后不断加上当前最大数乘上当前最大出现次数，贪心得到最大排序后的和ans，答案即为ans-res。

3.Ac_code

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static int N=100010;
    static int[] a=new int[N];
    static long[] s=new long[N];
    //差分数组
    static long[] g=new long[N];
    static int n;
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws IOException {
        n=Integer.parseInt(br.readLine());
        String[] v=br.readLine().split(" ");
        for (int i = 1; i <=n; i++) {
            a[i]=Integer.parseInt(v[i-1]);
            s[i]=s[i-1]+a[i];
        }
        int m=Integer.parseInt(br.readLine());
        long res=0;
        for (int i = 0; i < m; i++) {
            v=br.readLine().split(" ");
            int l=Integer.parseInt(v[0]);
            int r=Integer.parseInt(v[1]);
            g[l]++;
            g[r+1]--;
            res+=s[r]-s[l-1];
        }
        for (int i = 1; i <=n; i++) {
            g[i]+=g[i-1];
        }
        long ans=0;
        Arrays.sort(a);
        Arrays.sort(g);
        int pre=g.length-1;
        while (g[pre]!=0){
            ans+=g[pre] *a[pre];
            pre--;
        }
        System.out.println(ans-res);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

C++

#include
using namespace std;
typedef long long LL;
const int N = 200010;

int n, m;
LL a[N], s[N], g[N];
void solve()
{
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		s[i] += s[i - 1] + a[i];
	}
	cin >> m;
	LL res = 0;
	for (int i = 0; i < m; ++i)
	{
		int l, r;
		cin >> l >> r;
		g[l]++, g[r + 1]--;
		res += s[r] - s[l - 1];
	}
	for (int i = 1; i <= n; i++) {
		g[i] += g[i - 1];
	}
	LL ans = 0;
	sort(a + 1, a + n + 1);
	sort(g + 1, g + n + 1);
	int pre = n;
	while (g[pre] != 0) {
		ans += g[pre] * a[pre];
		pre--;
	}
	cout<<ans-res<<'\n';
}
int main()
{
	ios_base :: sync_with_stdio(false);
	cin.tie(nullptr);
	int t = 1;
	while (t--)
	{
		solve();
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47