| 题目名称 | 516. 求和 |
|---|---|
| 输入输出 | suma.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 常庆卫
于2010-11-19加入修改该题
|
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：70， 提交：170， 通过率：41.18% | ||||
|
胡嘉兴 |
100 | 0.222 s | 1.26 MiB | C++ |
|
胡嘉兴 |
100 | 0.225 s | 1.23 MiB | C++ |
|
胡嘉兴 |
100 | 0.232 s | 1.07 MiB | C++ |
|
马凯 |
100 | 0.264 s | 2.22 MiB | C++ |
|
陈亦凡 |
100 | 0.269 s | 0.31 MiB | C++ |
|
vampire |
100 | 0.281 s | 0.62 MiB | C++ |
|
雷雨豪 |
100 | 0.285 s | 0.30 MiB | C++ |
|
谢兴宇 |
100 | 0.291 s | 1.27 MiB | C++ |
|
Rivendel |
100 | 0.306 s | 0.70 MiB | C++ |
|
1 |
100 | 0.307 s | 0.34 MiB | C++ |
| 本题关联比赛 | |||
| 20101119 | |||
| 关于 求和 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
1a辣
CSU_Turkey
2017-12-18 22:04
8楼
| ||||
|
二分
サイタマ
2017-10-31 10:03
7楼
| ||||
|
| ||||
|
pbds大法好
| ||||
|
k和p读反了调了好久。。
_Itachi
2016-08-08 17:37
4楼
| ||||
|
treap1A
| ||||
|
平衡树做法：先求得前缀和，再取余，之后从前往后加入平衡树。对于每个j，找到i使得 s[j]-s[i-1] 或（s[i]-s[j-1])%P 大于K，且最小。
复杂度：O(nlogn) 滚学校去了，相当苦逼没时间写代码了 :( Chenyao2333
2013-11-17 16:07
2楼
| ||||
|
K P ai数据与实际范围不符，请修改题目描述 @cstdio
| ||||
【问题描述】
给出一个数列A1，A2…．，An和K，P。
设Sij=Ai+Ai+1+…+Aj
Anaswer=min{Si,j mod P | si,j mod P≥K)，其中i≤j，(si,j mod P | si,j mod P≥K}非空。
【输入格式】
第一行一个正整数n，K，P。
第二行n个整数，表示一个数列A1，A2，…，An
【输出格式】
在第一行输出Answer。
【输入样例】
7 2 17
12
13
15
11
16
26
11
【输出样例】
2
【数据范围】
在100％的数据中，1<n<100000，1<K，P，ai<108，i=1，2…n