蓝桥杯2022年第十三届省赛真题-重新排序

1486 阅读 0 评论 0 点赞

原题链接：蓝桥杯2022年第十三届省赛真题-重新排序

解题思路：
```cpp
定义a数组来存储原数组。
定义cnt数组来统计每个数出现的次数。
定义差分数组diff来求出cnt。
将a和cnt中对应位置的数值相乘，累加起来就是原数组的查询结果sum1。
对于最优结果，将cnt和a降序排序，然后将a和cnt中对应位置的数值相乘，累加起来就是最优数组的查询结果sum2。
输出sum2-sum1即可。
```
注意事项：
```cpp
不能使用暴力计算cnt，否则时间复杂度是O(n^2)，会超时。您可以使用差分的方法来计算cnt，这样时间复杂度就会降低到O(n)。
注意开long long，否则会爆int。
注意数据范围，否则可能会数组越界。
```
完整代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long

// 定义常量 N
const int N = 1e6 + 5;

// 定义数组 a 和 cnt，分别存储原数组的数值和每个数出现的次数
int a[N] = {};
ll cnt[N] = {};

// 定义差分数组 diff
ll diff[N] = {};

// 定义变量 n 和 m
int n, m;

int main() {
	// 读入 n 和原数组 a
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];

// 读入 m
	cin >> m;

// 定义变量 l 和 r，分别表示查询的左右端点
	int l, r;

// 定义 sum1 和 sum2，分别表示原数组和最优数组的总和
	ll sum1 = 0, sum2 = 0;

// 遍历所有的查询
	while (m--) {
		// 读入查询的左右端点
		cin >> l >> r;

// 对差分数组 diff 进行差分
		diff[l]++;
		diff[r + 1]--;
	}

// 计算 cnt 数组
	for (int i = 1; i <= n; i++) {
		cnt[i] = cnt[i - 1] + diff[i];
	}

// 计算原数组的总和
	for (int i = 1; i <= n; i++) sum1 += a[i] * cnt[i];

// 对 a 和 cnt 数组排序
	sort(a + 1, a + 1 + n);
	sort(cnt + 1, cnt + 1 + n);

// 计算最优数组的总和
	for (int i = 1; i <= n; i++) sum2 += a[i] * cnt[i];

// 输出答案
	cout << sum2 - sum1 << endl;

return 0;
}
```

0.0分

2 人评分

本文分类：题解列表
浏览次数：1486 次浏览
发布日期：2023-01-02 14:23:48
本文链接：https://blog.dotcpp.com/a/92693

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

蓝桥杯2022年第十三届省赛真题-重新排序

评论列表共有 0 条评论

发表评论取消回复

蓝桥杯2022年第十三届省赛真题-重新排序

1052: [编程入门]链表合并 自己记录

1676: 数据结构-链表的基本操作 自己记录

2025.7.4刷题记录

7月4号刷题记录yyyyyyyyyyyyyyyyyyy

评论列表 共有 0 条评论

发表评论 取消回复

1052: [编程入门]链表合并自己记录

1676: 数据结构-链表的基本操作自己记录

评论列表共有 0 条评论

发表评论取消回复