🌟差分、加法排序不等式(贪心)
🍎解题思路
1.首先利用差分
统计出每个数字被加的次数$c_i$
2.接着对原数组结算初始的总和$sum_1=\sum{a_i \times c_i}$
3.排序$a、c$数组,使得越大的被加次数对应越大的数字,贪心使得总和最大,求得$sum_2=\sum{sorted\_a_i \times sorted\_c_i}$
4.输出$sum_2 - sum_1 $即为总和最大增加了多少
🍭技巧
1.差分统计区间内数字被加的次数
2.加法排序不等式:两组升序数组对应数字相乘后相加,总和一定为最大值
🍇时间复杂度
$O(NlogN)$
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = a;i < b;i ++)
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int a[N], c[N]; //原数组、原数组中每个数字被加的次数
int n;
int main()
{
cin >> n;
rep(i, 1, n + 1) scanf("%d", &a[i]);
int m; cin >> m;
while (m -- )
{
int l, r;
scanf("%d%d", &l, &r);
c[l]++, c[r + 1] --; //差分统计区间内的数字被加上的次数
}
//差分后还原,统计的次数数组
rep(i, 1, n + 1) //结算每个数字被加的次数
c[i] += c[i - 1];
LL sum1 = 0; //初始时的总和
rep(i, 1, n + 1)
sum1 += (LL) a[i] * c[i]; //结算初始时的区间总和
//———— 重新排序 ———— 越大的数字和越大的加和次数相乘(贪心:局部最优到全局最优)
sort(a + 1, a + 1 + n);
sort(c + 1, c + 1 + n);
LL sum2 = 0;
rep(i, 1, n + 1)
sum2 += (LL) a[i] * c[i];
cout << sum2 - sum1;
return 0;
}