AcWing 4655. 重新排序

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 4655. 重新排序原题链接中等

作者：

JcWing , 2023-01-04 21:26:23 , 所有人可见 , 阅读 4586

81

17

题目描述

给定一个数组 $A$ 和一些查询 $L _ i, R _ i$，求数组中第 $L _ i$ 至第 $R _ i$ 个元素之和。

小蓝觉得这个问题很无聊，于是他想重新排列一下数组，使得最终每个查询结果的和尽可能地大。

小蓝想知道相比原数组，所有查询结果的总和最多可以增加多少?

输入格式

输入第一行包含一个整数 $n$。

第二行包含 $n$ 个整数 $A _ 1, A _ 2, \ldots, A _ n$，相邻两个整数之间用一个空格分隔。

第三行包含一个整数 $m$ 表示查询的数目。

接下来 $m$ 行，每行包含两个整数 $L _ i$、$R _ i$，相邻两个整数之间用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

数据范围

对于 $30 \%$ 的评测用例，$n, m \le 50$；
对于 $50 \%$ 的评测用例，$n, m \le 500$；
对于 $70 \%$ 的评测用例，$n, m \le 5000$；
对于所有评测用例，$1 \le n, m \le 10 ^ 5$，$1 \le A _ i \le 10 ^ 6$，$1 \le L _ i \le R _ i \le n$。

输入样例：

输出样例：

样例解释

原来的和为 $6 + 14 = 20$，重新排列为 $(1, 4, 5, 2, 3)$ 后和为 $10 + 14 = 24$，增加了 $4$。

解题思路

Part 1：贪心

我们可以累计每个 $A _ i$ 的被求和次数 $c _ i$。容易贪心得到，被求和次数越多的肯定得放越大的数（可用邻项交换证明）。

我们可以先统计原来的求和的总和 $sum$，再给 $A$ 数组和统计求和次数的数组 $\mathbf {c}$ 从小到大排好序，最后依次相乘起来即 $\mathbf {\sum \limits _ {i = 1} ^ n a _ i c _ i}$ 减去原来的总和 $\mathbf {sum}$ 便是答案。

Part 2：差分

统计求和次数时注意到只有修改操作而没有查询操作，于是可以用差分来维护。

具体地，我们建立一个都为 $0$ 的差分数组 $b$，当 $l \sim r$ 这段区间被求和时，就 将 $\mathbf {b _ l}$ 加上 $\mathbf 1$，$\mathbf {b _ {r + 1}}$ 减去 $\mathbf 1$ 就可以了。

注意：原来的总和和最大总和都要用 long long 来存储。

时间复杂度：$\Theta (n \log n)$。

AC Code

#include <iostream>
#include <algorithm>
#define N 100005
using namespace std;

int n, m, l, r, a[N], b[N];
long long sum, ans;

int main ()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        cin >> a[i];
    }
    cin >> m;
    while (m --)
    {
        cin >> l >> r, b[l] ++, b[r + 1] --; // 同时处理差分
    }
    for (int i = 1; i <= n; i ++)
    {
        b[i] += b[i - 1], sum += (long long) a[i] * b[i]; // 先得到数组 c（仍存放在数组 b 中），在顺便统计原来的总和 sum
    }
    sort (a + 1, a + n + 1), sort (b + 1, b + n + 1); // 分别排序
    for (int i = 1; i <= n; i ++)
    {
        ans += (long long) a[i] * b[i]; // 加上依次相乘的和
    }
    cout << ans - sum; // 答案即是依次相乘总和 - sum
    return 0;
}

感谢观看！

上一篇

下一篇

$$\href {/blog/content/29204/} {\color {fuchsia} {【寒假每日一题】题解}}$$

38 评论

大瓜娃子 2023-01-05 09:26

贴一个Python的

'''
被求和次数越多的肯定得放越大的数
'''
def slove():
    N = 10**5 + 10
    s = [0] * N #前缀和数组
    b = [0] * N #差分数组 恢复之后就是每个数字出现的次数
    temp = 0
    n = int(input())
    a = list(map(int,input().split()))
    a.insert(0,0)
    for i in range(1,n+1): s[i] = s[i-1] + a[i]#前缀和

    m = int(input())
    for _ in range(m):
        l,r = map(int,input().split())
        temp += s[r] - s[l-1]#(l,r)的和
        b[l] += 1#差分
        b[r+1] -= 1

    for i in range(1,n+1): b[i] += b[i-1] #求每个位置出现的次数

    a[1:] = sorted(a[1:],reverse=True) #原数组排序
    b[1:] = sorted(b[1:],reverse=True) #差分数组排序
    # print(a[1:n+1])
    # print(b[1:n+1])
    res = 0
    for i in range(1,n+1): #贪心 将大的数放到出现位置最多的地方
        res += a[i]*b[i]
    print(res - temp) #求增加的值

slove()

敲完代码睡大觉 2023-01-05 10:41

python版本的好清爽，好优雅！

lrs_0 8个月前

为啥要翻转排序啊？

lrs_0 8个月前

这个题要不是翻转排序的话就错了😂

真我Elysia 2023-01-05 10:18

差分真是遇到一次不会一次，麻了呀

Mr.Az 2023-01-05 19:19

差分其实就是把一段数加上同一个数化成了变化两个位置的差分数组的数的操作，本质是转化操作，让他更快

JcWing 2023-01-05 19:23 回复了 Mr.Az 的评论

Orz

Mr.Az 2023-01-05 20:34 回复了 JcWing 的评论

我是java同学 2023-01-08 15:35

想知道为什么要求前缀和，差分后每个区间不是都加上相应需要处理的次数了吗

胡歌-此生不换 2023-03-16 09:14

这里用差分的作用是方便求每一个Ai对应被加了多少次 (他这里结果还是放在了b数组里)。因为需要每一个数被加的次数 (添加数的总次数是不变的)。

我是java同学 2023-03-16 20:10 回复了胡歌-此生不换的评论

感谢感谢，现在已经理解了，以前理解得比较浅显，惭愧~

内蒙古最后一只铁匠 2023-01-05 11:17

long long 虐我千百遍

Chickee 2023-01-04 22:25

给a数组开了一个前缀和s, 处理m次询问的时候让sum += s[r] - s[l - 1];
莫名几秒有个点segment fault qwq

废物宝宝 2023-01-04 23:43

如果开的是int类型的前缀和数组会爆吧开long long s[N]不会出现错误的

Chickee 2023-01-05 21:39 回复了废物宝宝的评论

哥们开的是__int128的呜呜呜

Do2eM0N 2023-05-24 13:22

### 感谢分享
我又加了一个数组，三个区分开了。

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int n,m;
int l,r;
typedef long long ll;

const int N = 100010;
// 原数组，原数组的前缀和数组，差分数组记录每个数的使用次数
ll a[N],b[N],c[N];
int main(void){
    cin >> n;
    for(int i = 1 ; i <= n;i++){
        cin >> a[i];
        b[i] = b[i-1] + a[i];
    }
    cin >> m;
    ll old_sum = 0;
    for(int i = 1;i <= m;i++){
        cin >> l >> r;
        // 根据差分求得每个数被使用的次数
        c[l]++;
        c[r+1]--;

        old_sum += b[r]-b[l-1];
    }

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

        c[i] += c[i-1];
    }
    sort(a+1,a+1+n);
    sort(c+1,c+1+n);

    ll new_sum = 0;
    for(int i = 1; i <= n;i++){
        new_sum += (ll)a[i] * c[i];
    }
    // cout << old_sum <<" " << new_sum << endl;
    cout <<new_sum - old_sum <<endl;

    return 0;   
}