CF276C Little Girl and Maximum Sum 题解

题目链接

题目大意

通过修改序列 \(a\) 中的数的顺序，使

最大，并输出它的值。

思路

一道简单贪心 \(+\) 差分，通过差分的优秀的 \(O(1)\) 区间修改能力帮助我们求出每个位置在询问中询问的次数，进行排序，最后次数较多的就让值较大的数来，以此类推。

AC Code

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+10;
long long n,q,a[MAXN],b[MAXN],s[MAXN];
long long  sum;
template <typename T> inline void read(T &in) {
	in=0;int fh=1;char ch=getchar();
	while(!isdigit(ch)) {
		if(ch=='-') fh=-1;
		ch=getchar();
	}
	while(isdigit(ch)) in=(in<<1)+(in<<3)+(ch^48),ch=getchar();
	in*=fh;
}
template <typename T,typename... Ts> inline void read(T &in,Ts&... ins) {read(in),read(ins...);}
template <typename T> inline void write(T out) {
	static char str[20];int top=0;
	if(out<0) putchar('-'),out-=2*out;
	do{str[++top]=out%10+48,out/=10;} while(out);
	while(top) putchar(str[top--]);
	putchar('\n');
}
template <typename T,typename... Ts> inline void write(T out,Ts... outs) {write(out),write(outs...);}
int main(){
	read(n,q);
	for(int i=1;i<=n;i++) read(a[i]);
	while(q--){
		int l,r;
		read(l,r);
		b[l]++;
		b[r+1]--;
	}
	for(int i=1;i<=n;i++) s[i]=s[i-1]+b[i];
	sort(a+1,a+n+1);
	sort(s+1,s+n+1);
	for(int i=1;i<=n;i++) sum=sum+(a[i]*s[i]);
	cout<<sum;
	return 0;
}