|
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;
- }
复制代码
|
|