蓝桥杯2022年第十三届省赛真题-重新排序(贪心，差分数组)

解题思路:

注意事项:

参考代码:

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5 + 5;

int n;

ll a[N];

int num[N] = {0};

ll sum[N] = {0};

int main()

{

    int n;

    cin >> n;

    for (int i = 1; i <= n; i++) {

        cin >> a[i];

        sum[i] = sum[i-1] + a[i];

    }

    int m;

    cin >> m;

    ll sum1 = 0;

    int left, right;

    for (int i = 0; i < m; i++) {

        cin >> left >> right;

        sum1 += sum[right] - sum[left-1];

        num[left]++;

        num[right + 1]--;

    }

    for (int i = 1; i <= n; i++) {

        num[i] += num[i-1];

    }

    sort(a + 1, a + n + 1);

    sort(num + 1, num + n + 1);

    ll sum2 = 0;

    for (int i = 1; i <= n; i++) {

        sum2 += a[i] * num[i];

    }

    cout << sum2 - sum1 << endl;

    return 0;

}