余定成

用户名：dotcpp0598358

访问量：1522

签　名：

孙蕾，我好喜欢你啊，为了你我要把键盘敲烂！

等　　级
排　　名	87
经　　验	7589
参赛次数	1
文章发表	39
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

我是余定成

TA的其他文章

连续出现的字符
浏览：71

字符串判等（C++）
浏览：46

字符串匹配问题(strs)
浏览：119

你可能喜欢

C语言程序设计教程（第三版）课后习题5.6 （Java代码）

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

　　作者: 余定成　　　　发表时间：2023-01-02 14:23:48 浏览：263　|　评论：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分

3 人评分

C语言网提供「C语言、C++、算法竞赛、真题百练、Python课程」在线课程，全部由资深研发工程师或ACM金牌大佬亲授课，更科学、全面的课程体系，以在线视频+在线评测的学习模式学习，学练同步，拒绝理论派，真正学会编程！还有奖学金等增值福利等你！

余定成

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （Java代码）

图形输出（Java代码）

C语言程序设计教程（第三版）课后习题8.6 （C++代码）

C语言程序设计教程（第三版）课后习题7.5 （C++代码）

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

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题8.8 （C++代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

小明A+B （C语言代码）

校门外的树（C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

WU-拆分位数（C++代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

余定成

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （Java代码）

图形输出 （Java代码）

C语言程序设计教程（第三版）课后习题8.6 （C++代码）

C语言程序设计教程（第三版）课后习题7.5 （C++代码）

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

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题8.8 （C++代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

小明A+B （C语言代码）

校门外的树 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

WU-拆分位数 （C++代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

图形输出（Java代码）

　　评论区

校门外的树（C语言代码）

WU-拆分位数（C++代码）