计科余定成

用户名：dotcpp0598358

访问量：15772

签　名：

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

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

　　自我简介：

我是余定成

TA的其他文章

刻录光盘（c++）
浏览：66

你可能喜欢

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

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

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

5 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

计科余定成

TA的其他文章

你可能喜欢

格式错误一万年，，有没有过了的来看看（终于过了）

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

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

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

C语言训练-排序问题<1> （C语言代码）

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

评论区

精彩推荐

奖学金（C++代码）

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

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

WU-输出正反三角形（C++代码）

用筛法求之N内的素数。（C语言代码）

字符逆序（C语言代码）

A+B for Input-Output Practice （C语言代码）

DNA （C语言代码）

Quadratic Equation （C语言代码）

字符串比较（C语言代码）

计科余定成

TA的其他文章

你可能喜欢

格式错误一万年，，有没有过了的来看看（终于过了）

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

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

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

C语言训练-排序问题<1> （C语言代码）

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

评论区

精彩推荐

奖学金 （C++代码）

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

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

WU-输出正反三角形 （C++代码）

用筛法求之N内的素数。 （C语言代码）

字符逆序 （C语言代码）

A+B for Input-Output Practice （C语言代码）

DNA （C语言代码）

Quadratic Equation （C语言代码）

字符串比较 （C语言代码）

　　评论区

奖学金（C++代码）

WU-输出正反三角形（C++代码）

用筛法求之N内的素数。（C语言代码）

字符逆序（C语言代码）

字符串比较（C语言代码）