|
|
10鱼币
本帖最后由 Ewan-Ahiouy 于 2023-8-25 12:01 编辑
区间求和与排序
题目描述
给定一个包含 n 个正整数的数组 a，你需要回答 t 个询问。每个询问给出两个整数 l 和 r，要求计算数组 a 在区间 [l, r] 内的元素之和，并让数组 [l, r] 部分从大到小排序，最后输出数组 a。
输入格式
第一行一个整数 n 。
第二行 n 个整数 a_i，用空格分隔。
第三行一个整数 t 。
接下来 t 行，每行两个整数 l_i, r_i，用空格分隔。
输出格式
每次查询返回区间 [l, r] 的和，并将数组 [l, r] 部分从大到小排序（排序不影响区间和，你可以想成两个数组，一个排序，一个求和），查询结束后最后返回数组 a （排序过的），用空格分隔。
输入输出样例
样例输入 #1
- 5
- 1 2 3 4 5
- 2
- 1 3
- 3 5[code]
- [b]样例输出 #1[/b]
- [code]6
- 12
- 3 2 5 4 1
样例输入 #2
- 10
- 2 4 6 8 10 1 3 5 7 9
- 5
- 1 10
- 5 6
- 2 8
- 4 9
- 3 7
样例输出 #2
- 55
- 11
- 37
- 34
- 28
- 10 9 8 7 6 5 4 3 2 1
样例解释
【样例 #1 解释】
第一行：为第一次询问，区间 [1, 3] 的和为6，并将数组 [1, 3] 区间进行降序排序。
第二行：为第二次询问，区间 [3, 5] 的和为12，并将数组 [3, 5] 区间进行降序排序。
第三行：查询结束，返回现在的数组。
数据范围
对于 100% 的数据， 1 ≤ n ≤ 10^5 ， 1 ≤ t ≤ 10^3 ， 1 ≤ l_i < r_i ≤ n，1 ≤ a_i ≤ 10^3。
测试链接 -> https://www.luogu.com.cn/problem/U332137
本帖最后由 zhangjinxuan 于 2023-8-25 11:18 编辑
排序不能优化，就懒得写前缀和了 
- #include <bits/stdc++.h>
- using namespace std;
- int n, a[100001], t, l, r, b[100001];
- bool cmp(const int &a, const int &b) {
- return a > b;
- }
- int main() {
- scanf("%d", &n);
- for (int i = 1; i <= n; ++i) {
- scanf("%d", &a[i]);
- b[i] = a[i];
- }
- scanf("%d", &t);
- while (t--) {
- scanf("%d%d", &l, &r);
- long long sum = 0;
- for (int i = l; i <= r; ++i) sum += a[i];
- sort(b + l, b + r + 1, cmp);
- printf("%lld\n", sum);
- }
- for (int i = 1; i <= n; ++i) {
- printf("%d ", b[i]);
- }
- return 0;
- }
|
|
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2023-8-25 10:55:47
置顶卡
千斤顶
显身卡
楼主
发表于 2023-8-25 11:07:00
不行，得加大强度
