| 题目名称 | 1553. 帮忙 |
|---|---|
| 输入输出 | helpz.in/out |
| 难度等级 | ★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 mouse
于2014-03-21加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：13， 提交：28， 通过率：46.43% | ||||
 OIdiot |
100 | 0.017 s | 1.08 MiB | C++ |
 TanAp0k |
100 | 0.019 s | 1.15 MiB | C++ |
 digital-T |
100 | 0.020 s | 1.46 MiB | C++ |
 HouJikan |
100 | 0.031 s | 1.08 MiB | C++ |
 苏轼 |
100 | 0.216 s | 0.54 MiB | Pascal |
 雪狼 |
100 | 0.235 s | 1.15 MiB | C++ |
 cstdio |
100 | 0.247 s | 1.07 MiB | C++ |
 Chenyao2333 |
100 | 0.347 s | 1.46 MiB | C++ |
 bigmingod |
100 | 0.366 s | 1.82 MiB | C++ |
|
bigmingod |
100 | 0.370 s | 1.82 MiB | C++ |
| 本题关联比赛 | |||
| 20140321 | |||
| 关于 帮忙 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
动归+枚举不选的
 minecart
2014-10-24 20:09
6楼
| ||||
|
回复 @稠翼 :
哇塞....给O(n)的跪了........这道题竟然能又被翻出来.....话说...我连当时log做法都忘了怎么做了=.=(我是傻逼.....) Chenyao2333
2014-10-21 21:42
5楼
| ||||
|
回复 @Chenyao2333 :
记录前缀和，先枚举出长度为k的最大平均数的子段，再向左右扩展，看是否大于当前值。我被前缀弄晕了、、不打了  稠翼
2014-10-21 19:25
4楼
| ||||
|
单调队列不是O（n）吗QAQ
| ||||
|
回复 @Chenyao :
在这里，你可以去找一个叫李明杰的人要证明 | ||||
|
只会O(log(max_weight)n)的做法
据说有O(n)的做法? | ||||
【题目描述】
在高考研讨会上，随着 z 同学对 zn 了解的深入，发现她不仅是一个善良的女孩子，还是一个很勤劳的女生，哇塞，这样棒的女生在21世纪真是太难遇到了，要是可以娶到这样的女生，小 z 陷入了无限的 yy 中。
高考研讨会进入了尾声，校长一声令下，搬椅子喽~~~~，只见平时道貌岸然的那些所谓的好学生们一听要干活全跑了,shit~~!!操场上只剩 zn 与 z 同学了，面对成千上万的椅子， 肿么办~~小 z 突然意识到现在正是奥赛课啊，于是他想到了 hzoi2009的兄弟们，果然,当小 z 跑到机房，说明来意后，hzoi2009的兄弟们（还有个妹子）当时貌似在考试，但都没有半点 迟疑，立马跟随小 z 下楼（小 z 一直把这件事记在心中，现在回想起来还有点小感动哈）
面对成千上万的椅子，当然不能用蛮力一个一个的搬了，校长大人提供了一种搬运车。 椅子们是排成一排的，搬运车一次必须搬不少于k个的连续的椅子，消耗的机油为所搬椅子重量的平均值（总重量比椅子个数）。小 z 想知道搬一次最多能耗费多少机油，好向校长报销机油费.
【输入格式】
第一行：整数n（代表椅子数）与k（一次搬的最少的椅子数） ；
接下来n行，每行一个整数wi,代表椅子的重量。
【输出格式】
搬一次可能耗费的最多的机油数*1000（结果取整）
【样例输入】
10 6
6
4
2
10
3
8
5
9
4
1
【样例输出】
6500【提示】
对于30%的数据 0<k<n≤1000
对于100%的数据 0<k<n<100000
0<wi≤2000
【来源】
在此键入。