【蓝桥杯每日一题】重新排序

重新排序

2024-12-8 蓝桥杯每日一题 重新排序 前缀和 差分

题目大意

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

小蓝觉得这个问题很无聊, 于是他想重新排列一下数组, 使得最终每个查 询结果的和尽可能地大。小蓝想知道相比原数组, 所有查询结果的总和最多可 以增加多少?

解题思路

首先看到题一定会想到前缀和，因为要求数组中某一个区间的和。

分析这个题，想要某些区间里的和达到最大，那么可以让那些重合计算的位置能够交换到最大的值，以此达目的。

然后就是计算每一个位置的使用使用次数，可以通过差分，这里涉及到对某些区间的一个 +1 。

最后想要给这些使用次数最多的分配到可行的最大值，那么可以通过排序，将原数组和使用的次数都进行一个排序，那么这时候就满足上述那个要求；然后分别计算两次的总和相减即可。

举例：

1 2 3 4 5    	1 3   2 5
1 2 2 1 1 排序：	
1 2 3 4 5 
1 1 1 2 2

Accepted

//  不开 long long 见祖宗
#include <bits/stdc++.h>
using namespace std;typedef long long ll;
const int N = 100010;
ll a[N],b[N],c[N];
ll n,m;void diff(int l,int r) {b[l] += 1;b[r + 1] -= 1;
}int main()
{cin>>n;for(int i = 1 ;i <= n ;i++ ) {cin>>a[i];c[i] = c[i-1] + a[i];}cin>>m;ll cnt = 0;for(int i = 1;i <= m;i++) {int l,r;cin>>l>>r;diff(l,r);cnt += c[r] - c[l-1];}for(int i = 1;i <= n;i++) {b[i] = b[i-1] + b[i];}sort(b+1,b+n+1);sort(a+1,a+n+1);ll pre = 0;for(int i = 1;i <= n;i++) {pre += a[i] * b[i];}cout<<pre - cnt<<endl;return 0;
}

思考

当时的思考已经分析到了使用次数，就差最后的一个神来之笔——排序求解。

备注

想要一起备赛的小伙伴可以私信加我的联系方式！