A40889. 重新排序本题总分：20 分【问题描述】给定一个数组 A 和一些查询 Li, Ri，求数组中第 Li 至第 Ri 个元素之和。小蓝觉得这个问题很无聊，于是他想重新排列一下数组，使得最终每个查询结果的和尽可能地大。小蓝想知道相比原数组，所有查询结果的总和最多可以增加多少?【
填空题
困难
知识点
题目描述
重新排序
本题总分：20 分
【问题描述】
给定一个数组 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
参考答案
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
struct set{
int L;
int R;
};
bool cmp(int a,int b){
return a>b;
}
int main() {
int size,czNum,res1=0,res2=0;
cin>>size;
int data[size+1],flag[size+1];
memset(data,0,sizeof(data));
memset(flag,0,sizeof(flag));
for (int i = 1; i <=size; ++i) {
cin>>data[i];
}
cin>>czNum;
set cz;
for (int i = 0; i < czNum; ++i) {
cin>>cz.L>>cz.R;
for (int j = cz.L; j <=cz.R ; ++j) {
flag[j]++;
}
}
for (int i = 1; i <=size ; ++i) {
res1+=data[i]*flag[i];
}
sort(data+1,data+size+1, cmp);
sort(flag+1,flag+size+1,cmp);
for (int i = 1; i <=size ; ++i) {
res2+=data[i]*flag[i];
}
cout<<res2-res1;
return 0;
}
上一题
下一题