CF276C Little Girl and Maximum Sum

Coros_Trusds · 2022-03-08 22:25:21 · 题解

题目大意

给定长为 n 的序列，你可以对其任意排序。再给出 m 个询问，每一次询问询问区间和，请制定策略使得所有询问之和最大。

题目分析

这是一道贪心题。

显然要在询问最多的区间放最大的数，这样能让全局最优。

所以我们先把原序列排序，然后维护一个空序列，每一次询问 [l,r] 就把空序列上 [l,r] 区间内的数加一，最后对这个序列也进行一次排序。答案就是 \sum\limits_{i=1}^na_i\times b_i。

区间加一可以用差分维护。时间复杂度 \mathcal{O(n\log n)}，瓶颈在排序。

注意开 long long。

代码

//2022/3/8
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <climits>//need "INT_MAX","INT_MIN"
#include <cstring>//need "memset"
#include <numeric>
#include <algorithm>
#define int long long
#define enter() putchar(10)
#define debug(c,que) cerr << #c << " = " << c << que
#define cek(c) puts(c)
#define blow(arr,st,ed,w) for(register int i = (st);i <= (ed); ++ i) cout << arr[i] << w;
#define speed_up() cin.tie(0),cout.tie(0)
#define mst(a,k) memset(a,k,sizeof(a))
#define Abs(x) ((x) > 0 ? (x) : -(x))
const int mod = 1e9 + 7;
inline int MOD(int x) {
    while (x < 0) x += mod;
    while (x >= mod) x -= mod;
    return x;
}
namespace Newstd {
    char buf[1 << 21],*p1 = buf,*p2 = buf;
    inline int getc() {
        return p1 == p2 && (p2 = (p1 = buf) + fread(buf,1,1 << 21,stdin),p1 == p2) ? EOF : *p1 ++;
    }
    inline int read() {
        int ret = 0,f = 0;char ch = getc();
        while (!isdigit(ch)) {
            if(ch == '-') f = 1;
            ch = getc();
        }
        while (isdigit(ch)) {
            ret = (ret << 3) + (ret << 1) + ch - 48;
            ch = getc();
        }
        return f ? -ret : ret;
    }
    inline void write(int x) {
        if(x < 0) {
            putchar('-');
            x = -x;
        }
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace Newstd;
using namespace std;

const int ma = 2e5 + 5;
int a[ma],sub[ma],sum[ma];
int n,m;
#undef int
int main(void) {
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
#endif
    #define int long long
    n = read(),m = read();
    for (register int i = 1;i <= n; ++ i) a[i] = read();
    sort(a + 1,a + n + 1);
    for (register int i = 1;i <= m; ++ i) {
        int l = read(),r = read();
        sub[l] ++,sub[r + 1] --;
    }
    for (register int i = 1;i <= n; ++ i) sum[i] = sum[i - 1] + sub[i];
    sort(sum + 1,sum + n + 1);
    int ans = 0;
    for (register int i = 1;i <= n; ++ i) {
        ans += a[i] * sum[i];
    }
    printf("%lld\n",ans);

    return 0;
}