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

拼搏现实的明天。 2023-09-28 23:23 11阅读 0赞

#### 目录 ####

*  1.重新排序
 *   *  1.题目描述
     *  2.输入格式
     *  3.输出格式
     *  4.样例输入
     *  5.样例输出
     *  6.样例说明
     *  7.数据范围
     *  8.原题链接
 *  2.解题思路
 *  3.Ac\_code
 *   *  Java
     *  C++

## 1.重新排序 ##

### 1.题目描述 ###

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

### 2.输入格式 ###

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

第二行包含  n n n 个整数  A 1 , A 2 , ⋯   , A n A\_\{1\}, A\_\{2\}, \\cdots, A\_\{n\} A1,A2,⋯,An , 相邻两个整数之间用一个空格分隔。  
第三行包含一个整数  m m m 表示查询的数目。

接下来  m m m 行, 每行包含两个整数  L i 、 R i L\_\{i\} 、 R\_\{i\} Li、Ri, 相邻两个整数之间用一个空格分隔。

### 3.输出格式 ###

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

### 4.样例输入 ###

5  
1 2 3 4 5  
2  
1 3  
2 5

### 5.样例输出 ###

### 6.样例说明 ###

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

### 7.数据范围 ###

1 ≤ n , m ≤ 1 0 5 , 1 ≤ A i ≤ 1 0 6 , 1 ≤ L i ≤ R i ≤ 1 0 6 1≤n,m≤10^5,1≤Ai ≤10^6 ,1≤Li ≤Ri ≤10^6 1≤n,m≤105,1≤Ai≤106,1≤Li≤Ri≤106 。

### 8.原题链接 ###

[重新排序][Link 1]

## 2.解题思路 ##

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

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

先统计出每个位置被统计的频率，也就是当查询区间为 \[ l , r \] \[l,r\] \[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);
        }
    }

### C++ ###

#include<bits/stdc++.h>
    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;
    }

[Link 1]: https://www.lanqiao.cn/problems/2128/learning/