1 条题解
-
0
题目大意
找出从第二项起所有等于其前面各项之和的元素。有命中时输出命中元素之和,否则输出全序列之和。
解题思路
处理第 项时,
prefix已累计了前 项。先比较,再把当前项加入prefix,这样下一轮开始时仍有同样的关系。用found单独记录是否命中,用matched_sum累计命中项。读完后prefix就是全序列之和。时间复杂度 ,额外空间复杂度 。易错点
易错点 说明 比较前先加上当前项 先比较再更新前缀和。 少判断最后一项 从第二项一直判断到第 项。 根据命中和是否为零决定分支 命中项可能为零或彼此抵消,用单独的标记。 累加使用 int两种和都用 long long。参考代码
#include <stdio.h> int main(void) { int n; long long prefix = 0, matched_sum = 0; int found = 0; scanf("%d", &n); for (int i = 1; i <= n; ++i) { long long value; scanf("%lld", &value); if (i > 1 && value == prefix) { matched_sum += value; found = 1; } prefix += value; } printf("%lld\n", found ? matched_sum : prefix); return 0; }
信息
- ID
- 648
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 6
- 标签
- 递交数
- 95
- 已通过
- 31
- 上传者
吉公网安备22010402001496号