5.依依的询问最小值 - 蓝桥云课

问题描述

依依有个长度为 n 的序列 a，下标从 1 开始。

她有 m 次查询操作，每次她会查询下标区间在 [li​,ri​] 的 a 中元素和。她想知道你可以重新排序序列 a，使得这 m 次查询的总和最小。

求你求出 m 次查询总和的最小值。

输入格式

第一行输入两个整数 n,m (1≤n,m≤105)，表示序列 a 的长度以及查询次数。

第二行输入 n 个整数 ai​ (1≤ai​≤105)，表示序列 a 中的元素。

接下来 m 行，每行输入两个整数 li​,ri​ (1≤li​≤ri​≤n)，表示询问的下标区间。

输出格式

输出仅一行，包含一个整数，表示 m 次查询总和的最小值。

样例输入

3 2
1 2 3
1 2
2 3

样例输出

7

思路：

方法一:

下标次数越多说明对应的数值就要最小，这样m 次查询总和就最小。所以我们要记录每一个下标出现的次数降序排序，输入数组的值升序排序。用sum记录它们一一对应相乘和相加即可。但是当m，n很大的时候时间复杂度很高，数值也很大，会失进度和超时。

代码如下：
 

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 1e5+10;
int n,m;
int arr[N];
int has[N];
bool compare(int a,int b)
{return a > b;
}
int main(void)
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n >> m;for(int i = 1 ; i <= n ; i++){cin >> arr[i];}int l,r;while(m--){cin >> l >> r;for(int j = l ; j <= r ; j++){has[j]++;}}sort(has + 1, has + 1 + n,compare);//对has数组降序 sort(arr + 1,arr + 1 + n);//对arr数组升序排序int sum = 0;for(int i = 1 ; i <= n ; i++){sum += arr[i] * has[i];	} cout << sum;} 

方法二：
面对这种区间问题，我们需要用到差分数组优化。差分数组可以很好的将一个区间同时增加，减少。对于这道题只有增加出现次数的下标。所以差分数组一开始都为0。待到全部区间操作完毕，用   dif[i] += dif[i - 1];  // 累加差分数组得到实际频率。得到实际数组。

代码如下：

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const ll N = 1e5+10;
ll n,m;
ll arr[N];
ll dif[N];
bool compare(ll a,ll b)
{return a > b;
}
int main(void)
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n >> m;for(ll i = 1 ; i <= n ; i++){cin >> arr[i];}ll l,r;while(m--){cin >> l >> r;dif[l] += 1;if(r+1 <= n)//注意边界dif[r+1] -= 1;	}//通过差分数组实现原本数组for (ll i = 1; i <= n; i++){dif[i] += dif[i - 1];  // 累加差分数组得到实际频率}sort(dif + 1, dif + 1 + n,compare);//对dif数组降序 sort(arr + 1,arr + 1 + n);//对arr数组升序排序ll sum = 0;for(ll i = 1 ; i <= n ; i++){sum += arr[i] * dif[i];	} cout << sum;}