摘要
Title: 4655. 重新排序
Tag: 差分
Memory Limit: 64 MB
Time Limit: 1000 ms

4655. 重新排序

题意

给定一个数组 A 和一些查询 Li,Ri，求数组中第 Li 至第 Ri 个元素之和。
小蓝觉得这个问题很无聊，于是他想重新排列一下数组，使得最终每个查询结果的和尽可能地大。
小蓝想知道相比原数组，所有查询结果的总和最多可以增加多少?
思路

查询的区间用差分处理，大的值乘频率高的，使值最大化

代码

c++

/*
* @Author: NEFU AB-IN
* @Date: 2023-01-05 11:59:15
* @FilePath: \Acwing\4655\4655.cpp
* @LastEditTime: 2023-01-05 12:11:37
*/
#include <bits/stdc++.h>
using namespace std;
#define N n + 100
#define int long long
#define SZ(X) ((int)(X).size())
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(nullptr);                                                                                                  \
    cout.tie(nullptr)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;

#undef N
const int N = 1e5 + 10;
int n, m, a[N], b[N];

// #undef int

signed main()
{
    IOS;
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    cin >> m;
    for (int i = 1; i <= m; ++i)
    {
        int l, r;
        cin >> l >> r;
        b[l]++;
        b[r + 1]--;
    }
    for (int i = 0; i <= n; ++i)
    {
        b[i] += b[i - 1];
    }
    int ans1 = 0, ans2 = 0;
    for (int i = 1; i <= n; ++i)
    {
        ans1 += (a[i] * b[i]);
    }
    sort(a + 1, a + 1 + n);
    sort(b + 1, b + 1 + n);

    for (int i = 1; i <= n; ++i)
    {
        ans2 += (a[i] * b[i]);
    }

    cout << ans2 - ans1;
    return 0;
}

python3

'''
Author: NEFU AB-IN
Date: 2022-04-09 09:28:11
FilePath: \Contest\f.py
LastEditTime: 2022-04-09 09:38:42
'''
n = int(input())
a = list(map(int, input().split()))

# 求原先的ans
s = [0] * (n + 2)
a = [0, *a]
for i in range(1, n + 1):
    s[i] = s[i - 1] + a[i]

a = sorted(a[1:], reverse=True)
a = [0, *a]

b = [0] * (n + 2)

m = int(input())
ans1 = 0
for i in range(m):
    l, r = map(int, input().split())
    b[l] += 1
    b[r + 1] -= 1
    ans1 += (s[r] - s[l - 1])

stk = []
for i in range(1, n + 1):
    b[i] += b[i - 1]
    stk.append(b[i])

stk.sort(reverse=True)
stk = [0, *stk]

ans = 0
for i in range(1, n + 1):
    ans += (a[i] * stk[i])
print(ans - ans1)

4655. 重新排序

题意

思路

代码