C. Little Girl and Maximum Sum【差分 / 贪心】

贪心，思路很简单。肯定是公共次数最多的，放最大的值。以此类推。
我们可以用差分来维护，快速的给区间加1。最后统计每一个点背统计的次数。
然后将数值按照从大到小。给出现次数多的点赋值构造数组。最后前缀和统计。

#include<bits/stdc++.h> using namespace std; const int N=1e5*2+10; typedef long long int LL; typedef pair<int,int> PII; LL a[N],b[N],c[N],s[N],n,m; vector<PII>ve,temp; void add(int l,int r) {b[l]+=1;b[r+1]-=1; } bool cmp(PII a,PII b){return a.first>b.first;} bool cmp1(int a,int b){return a>b;} int main(void) {cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];for(int i=0;i<m;i++){int l,r; cin>>l>>r;ve.push_back({l,r});add(l,r);}for(int i=1;i<=n;i++) b[i]+=b[i-1];for(int i=1;i<=n;i++) temp.push_back({b[i],i});sort(temp.begin(),temp.end(),cmp);sort(a+1,a+n+1,cmp1);for(int i=1;i<=n;i++) c[temp[i-1].second]=a[i];for(int i=1;i<=n;i++) s[i]=s[i-1]+c[i];LL sum=0;for(int i=0;i<m;i++){int l=ve[i].first,r=ve[i].second;sum+=s[r]-s[l-1];}cout<<sum;return 0; }

总结

以上是生活随笔为你收集整理的C. Little Girl and Maximum Sum【差分 / 贪心】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。