本文主要是介绍Codeforces 276C - Little Girl and Maximum Sum（题解），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
原题地址：https://codeforces.com/problemset/problem/276/C
分析：乍一看以为简单的 数组区间求和，快速 query，结果不是。
题目说，在给定的 q 组区间下，能否将数组调整成 某一种顺序，使得这 q 组区间查询结果 得到的所有结果之和，尽可能最大。
所以变成了：我们需要统计这 q 组区间查询下，哪些数组元素位置 pos 被区间命中的次数最多。
哪一个位置次数最多，那么把这个位置，给调整成数组的最大元素，次数第二多，此处数组值调整成数组的第二大元素，....，依此类推。
涉及三个技巧：
1.数组区间片段，快速求命中次数，采用一个 segmentStart，segmentEnd 标记数组，和一个标记变量 cur，采用累进方式，统计当前位置 arr[pos] 的命中次数。
2. 对元素在片段中的命中次数，以及 原数组，两个数组排序。然后结果是 occurence[i] * arraySortDesc[i] 累加之和。
3. 因为采用的是 Java 实现，测试集中有 20000 级别的 大数据量 input 用例，所以不能用一般的 `Scanner(System.in)`，而要用一个 Buffer 的 FasterReader 类，参考下方代码。
以下是完整 Java AC 代码。
// AC: 624 ms
// Memory: 11600 KB
// Array Segment count & Sort: We need to find the most frequency position, and assign with the maximum value of the array,
// then the next frequency position, and assign with the second maximum value of array.
// Notice: Using FasterReader class instead of `Scanner(System.in)`, otherwise the Java solution could TLE.
// T:O(nlogn), S:O(n)
//
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;public class Codeforces_0276C_Little_Girl_and_Maximum_Sum {private static class FastReader {BufferedReader br;StringTokenizer st;public FastReader() {br = new BufferedReader(new InputStreamReader(System.in));}String next() {while (st == null || !st.hasMoreElements()) {try {st = new StringTokenizer(br.readLine());} catch (IOException e) {e.printStackTrace();}}return st.nextToken();}int nextInt() {return Integer.parseInt(next());}long nextLong() {return Long.parseLong(next());}double nextDouble() {return Double.parseDouble(next());}String nextLine() {String str = "";try {str = br.readLine();} catch (IOException e) {e.printStackTrace();}return str;}}public static void main(String[] args) {FastReader sc = new FastReader();int n = sc.nextInt(), q = sc.nextInt();long ret = 0;Integer[] arr = new Integer[n];int[] segmentStart = new int[n], segmentEnd = new int[n];for (int i = 0; i < n; i++) {arr[i] = sc.nextInt();}for (int i = 0; i < q; i++) {int l = sc.nextInt(), r = sc.nextInt();segmentStart[l - 1]++;segmentEnd[r - 1]++;}int cur = 0;PriorityQueue<Integer> countOccurence = new PriorityQueue<>((o1, o2) -> o2 - o1);for (int i = 0; i < n; i++) {if (segmentStart[i] > 0) {cur += segmentStart[i];}if (cur > 0) {countOccurence.offer(cur);}if (segmentEnd[i] > 0) {cur -= segmentEnd[i];}}Arrays.sort(arr);int pos = n - 1;while (!countOccurence.isEmpty()) {int occurence = countOccurence.poll();ret += (long) occurence * arr[pos--];}System.out.println(ret);}
}
这篇关于Codeforces 276C - Little Girl and Maximum Sum（题解）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
