貪心，思路很簡單。肯定是公共次數最多的，放最大的值。以此類推。
我們可以用差分來維護，快速的給區間加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【差分 / 贪心】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。