Jettblue_jr 2022-12-09 11:46 采纳率: 100%
浏览 97
已结题

关于加权前缀和的问题

加权前缀和

时间限制:1.0s 内存限制:256.0MB 代码提交间隔:1分钟(现在可以提交)
问题描述
  给定一个长度为n的数列a以及q次询问。
  询问共有两种:
  询问1:给定x和y,询问第x个数至第y个数的和
  询问2:给定x和y,询问第x个数至第y个数的加权和。其中,区间内的第1个数的权重为1,第2个数的权重为2,以此类推。
输入格式
  第一行包含一个正整数n,表示数列长度。
  第二行共有n个非负整数,表示数列a。
  第三行包含一个正整数q,表示询问数量。
  随后q行,每行三个正整数k、x、y,用来描述询问。k表示询问的类型,x、y表示询问的区间。
输出格式
  共q行,每行一个整数,表示询问的答案。
样例输入
5
1 2 3 4 5
3
1 2 4
2 2 3
2 3 5
样例输出
9
8
26
数据规模和约定
  n, q<=100000,数列中的每个数不超过1000

#include <cstdio>
using namespace std;
int main() {
    long long n, k, z, x, y, a, i;
    scanf("%lld", &n);
    long long sum[n + 10] = {0}, num[n + 10] = {0}; 
    for (i = 1; i <= n; i++){
        scanf("%lld", &a);
        sum[i] = sum[i - 1] + a;
        num[i] = num[i - 1] + sum[i];
    }
    scanf("%lld", &k);
    for (i = 1; i <= k; i++){
        scanf("%d%lld%lld", &z, &x, &y);
        if (z == 1) printf("%lld\n", sum[y] - sum[x - 1]);
        else if (z == 2) printf("%lld\n", (y - x + 1) * sum[y] - (num[y - 1] - num[x - 2]));
    }
  return 0;
}
50分代码,求各位帮忙看看哪里有问题,正确指出问题的回答我会采纳的~
  • 写回答

2条回答 默认 最新

  • EUREKA-X 2022-12-09 13:28
    关注

    你计算加权的部分感觉有点复杂,我想是你把求和和录入数组放在了一起的原因,其实可以分开,这样方便也不容易出错。
    所以建议换这种更清晰好懂的写法:
    用数组a来存放数列的每一个项
    第二次输入1,i,j则
    循环累加ai+1到aj+1
    为2,i,j
    则循环r=i+1;r《j+1;r++
    s=s+(r-i)*ar
    望采纳

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论 编辑记录
查看更多回答(1条)

报告相同问题?

问题事件

  • 系统已结题 12月17日
  • 已采纳回答 12月9日
  • 创建了问题 12月9日

悬赏问题

  • ¥15 win32如何自绘编辑框的背景图片(语言-c++|操作系统-windows)
  • ¥15 c# 直接使用 c++ 写的 class
  • ¥15 微信夜间被转走了1w对,当天手机剪切板里就出现了这个乱码,有铁子可以看看是啥吗可以
  • ¥50 跑通github上的代码 深度学习 pytorch
  • ¥50 求写,批处理调用分区助手分区脚本
  • ¥15 求购HI3519AV100开发板
  • ¥15 请问1553 RT怎么测试,没有BC有方法吗
  • ¥100 业务编程如何选择学习方向和内容?
  • ¥15 wamp3.3.5安装完成后图标正常显示绿色,鼠标左右键点击图标均无反应。求解决方法。
  • ¥15 鼠标点击的这条记录了什么?