重新排序-蓝桥杯研究生组G题

@toc

1、问题描述

给定一个数组 A 和一些查询 $L_i,R_i$, 求数组中第 $L_i$ 至第 $R_i$个元素之和。

小蓝觉得这个问题很无聊, 于是他想重新排列一下数组, 使得最终每个查询结果的和尽可能地大。小蓝想知道相比原数组, 所有查询结果的总和最多可 以增加多少?

输入格式

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

第二行包含 n 个整数 $A_1,A_2,...A_n$, 相邻两个整数之间用一个空格分隔。

第三行包含一个整数 m 表示查询的数目。

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

输出格式

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

样例输入

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\le n,m\le 10^5,1\le A_i\le10^6,1\le L_i\le R_i\le 10^6$ 。

运行限制

• 最大运行时间：1s
• 最大运行内存: 512M

2、解题思路

题目想要重新排列之后的数组，使得每个查询结果尽可能大，最终的结果为重新排列之后的最大和减去重新排列之前的最大和。

我们不用一个个去加这些数字，我们只需要统计经过m次查询，每个位置上的数字被加了多少次就行，最后做个统计就行。我们的目的是计算出每个位置上的查询次数，也就是被加的次数，最后我们尽可能让数值比较大的数字被查询的次数最多就能满足最后的和最大。

根据每次给定的查询区间 $[L_i,R_i]$,我们将该区间中每个数字查询数字+1，为了统计每个数字的查询次数，我们需要实现区间加法，在这里使用差分数组实现。

要实现区间 $[L_i,R_i]$上+1，假设差分数组为b,只需要差分数组实现 $b[L_i]++,b[R_i+1]--$。然后最后对差分数组b求前缀和即可得到每个位置上被查询的次数。$s[j]= {\textstyle \sum_{i=1}^{j}b[i]} $

然后我们可以直接计算出重新排列之前的查询之和，让每个位置上的数字乘以它的查询次数即可。

贪心思想：我们的目的是查询之和最大，那么我们直接将原数组a和前缀和数组s都进行排序，然后对应位置相乘求和，这样就保证了较大的数字被查询的次数多一点，和也就最大了。

3、代码实现

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

public class Main {
    public static  StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public static void main(String[] args) throws IOException {
        int n = nextInt();
        int[] a = new int[n + 1];   //原数组
        int[] b = new int[n + 2];   //差分数组
        int[] s = new int[n + 1];   //前缀和数组
        for (int i = 1; i <=n ; i++) {
            a[i]=nextInt();
        }
        int m =nextInt();
        for (int i = 0; i <m ; i++) {
            int left = nextInt();
            int right = nextInt();
            //差分数组实现区间加法更新
            b[left]++;
            b[right+1]--;
        }
        //对差分数组求前缀和，得到每个数字的查询次数
        for (int i = 1; i <=n; i++) {
            s[i]=s[i-1]+b[i];
        }
        long sum1=0;    //原始和
        long sum2=0;    //重新排列数组之后的和
        for (int i = 1; i <=n; i++){   //计算原始和
            sum1+=(long)a[i]*s[i];    //元素值*查询次数
        }
        Arrays.sort(a);
        Arrays.sort(s);
        //sum2为贪心后的最大和
        for (int i = 1; i <=n ; i++) {
            sum2+=(long)a[i]*s[i];
        }
        //计算增加了多少
        System.out.println(sum2-sum1);
    }
    public static int nextInt() throws IOException {
        st.nextToken();
        return (int)st.nval;
    }
}

亲测这里不用java快读会超时

这个代码是可以AC的