1998. The old Padawan
Time limit: 0.5 second
Memory limit: 64 MB
Memory limit: 64 MB
Yoda: Use the Force. Yes. Now, the stone. Feel it. Concentrate!
Luke Skywalker is having exhausting practice at a God-forsaken planet Dagoba. One of his main difficulties is navigating cumbersome objects using the Power. Luke’s task is to hold several stones in the air simultaneously. It takes complete concentration and attentiveness but the fellow keeps getting distracted.
Luke chose a certain order of stones and he lifts them, one by one, strictly following the order. Each second Luke raises a stone in the air. However, if he gets distracted during this second, he cannot lift the stone. Moreover, he drops some stones he had picked before. The stones fall in the order that is reverse to the order they were raised. They fall until the total weight of the fallen stones exceeds k kilograms or there are no more stones to fall down.
The task is considered complete at the moment when Luke gets all of the stones in the air. Luke is good at divination and he can foresee all moments he will get distracted at. Now he wants to understand how much time he is going to need to complete the exercise and move on.
Input
The first line contains three integers: n is the total number of stones, m is the number of moments when Luke gets distracted and k (1 ≤ n, m ≤ 105, 1 ≤ k ≤ 109). Next n lines contain the stones’ weights wi (in kilograms) in the order Luke is going to raise them (1 ≤wi ≤ 104). Next m lines contain moments ti, when Luke gets distracted by some events (1 ≤ ti ≤ 109, ti < ti+1).
Output
Print a single integer — the number of seconds young Skywalker needs to complete the exercise.
Sample
5 1 4 1 2 3 4 5 4 |
8 |
Hint
In the first three seconds Luke raises stones that weight 1, 2 and 3 kilograms. On the fourth second he gets distracted and drops stones that weight 2 and 3 kilograms. During the next four seconds he raises all the four stones off the ground and finishes the task.
题意:
给出 n(1 ~ 10 ^ 5),m(1 ~ 10 ^ 5),k(1 ~ 10 ^ 9),代表给出 N 个球,后有 M 个停顿时间,每秒钟都会往上抛一个球,如果遇到的是停顿的时间,则不会往上抛球,但是会有球下降下来,直到下降下来的球的总重量大于 k,或者全部都掉下来了才继续抛球。输出过多少时间才会把所有的球给跑到天空中。
思路:
尺取法预处理当每个球不抛的时候会退回哪一个位置。后循环停顿的时间,维护该时间所需要抛的球是哪个,如果该停顿时间距离上一次停顿时间依然没有抛完所有的球的话,则退回刚刚预处理所需要抛球的位置,不断这样判断,直到判断到能完全抛完所有球为止。如果所有的停顿时间都停顿完了依然没有抛完的话,则最后的总时间还要加上剩下球的个数。
比赛的时候很烦躁,明明一开始就会做,但是被边界问题处理得很烦,后来也没有心思去 debug 了,以后一定要改进,切忌不能烦躁不能放弃,细心处理好边界问题。
AC:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAX = 100005; int num[MAX], stop[MAX], ans[MAX]; int main() { int n, m, k; scanf("%d%d%d", &n, &m, &k); for (int i = 1; i <= n; ++i) { scanf("%d", &num[i]); } int sum = 0, from = 1, t = 1; while (sum <= k && t <= n) { ans[t] = from; sum += num[t]; ++t; } for (t; t <= n; ++t) { while (sum - num[from] > k && from < t - 1) { sum -= num[from]; ++from; } ans[t] = from; sum += num[t]; } stop[0] = 0; for (int i = 1; i <= m; ++i) scanf("%d", &stop[i]); int sum_time = 0, now = 1; for (int i = 1; i <= m; ++i) { int need = n - now + 1; if (stop[i] - stop[i - 1] > need) { sum_time = stop[i - 1] + need; now = n; break; } else { now = now + stop[i] - stop[i - 1] - 1; now = ans[now]; sum_time = stop[i]; } } if (now != n) printf("%d\n", sum_time + (n - now + 1)); else printf("%d\n", sum_time); return 0; }
相关推荐
当前,Padawan.vim提供了基于文档注释和方法签名的方法和类的基本完成。 单击下面的图像,观看有关Padawan.vim已经可以执行的操作的简短视频。 要求 Padawan.vim要求: PHP 5.5以上 作曲家 带+ python的Vim 安装 ...
基于 DanF 的 PS2 控制器 PADAWAN 草图,该草图旨在允许使用 PS2、PS3、PS4 或 XBox 360 控制器,具体取决于草图开始时设置的编译选项。 使用 Arduino Mega ADK、Padawan Shield、AZIO Class 1 蓝牙 USB Dongle、PS...
就像这样: host$ git clone https://github.com/Dlimaun/padawan-vagrant.githost$ cd padawan-vagrant`host$ vagrant up您的虚拟机正在运行! \ o /让我们通过以下方式访问它: host$ vagrant ssh安装了什么没有...
padawan-learning:该存储库用于存储使用Padawan进行的编码练习
FrameWork-Padawans:Processo Padawan框架
Padawan-网络Rails 和 Android 社交网络
指导者飞跃 该项目旨在将技术职业改变者与导师联系起来,在那里他们可以观看导师的实时直播并与他们聊天。 他们还将能够与其他职业转变者的指导者一起享受视频办公时间。
” - 尤达Padawan项目是一个极简的教师构建程序,它为人们提供了必要的技能以用作javascript开发人员。 这是通过指导,自我学习,解决问题和建立应用程序来实现的。为什么? 除非应用知识,否则知识是无用的。 Web...
Symfony2插件 ...插件名称为mkusher/padawan-symfony ,因此您应使用此名称调用plugin add 。 跑步 到目前为止,更新服务映射的唯一方法是Generate Index 。 之后,您将能够获取服务列表和类型检测。
$ git clone https://github.com/DanielArturoAlejoAlvarez/Padawan.git [NAME APP] $ npm install $ npm start 请按照以下步骤操作,一切顺利! 重要: 编码 乌尔斯 ... const auth = require ( '../middlewares/...
TableauJS_API_101 Padawan Dojo JS API 101 类的 HTML 和 JS 代码您可以在此处找到有关使用 Tableau JS API 的介绍类的代码示例,为
padawan9002.github.io 这个不起眼的例子是试图展示我们可用的力量的一小部分。
react-es6-padawan-to-jedi-book:乌玛语入门简单版和完整版React USando ES6 e Babel
帕达万卡路里计算器 设置 您必须安装node.js和npm 。 打开项目目录并运行: npm install 启动程序: npm run start
myListTeam01 在HBSIS Ambev Padawan培训计划(2019年版)中开发的项目,移动类,模块Android。
游戏《 Padawan Adventures》是一个迷宫形状的游戏,角色必须找到进入下一个世界的正确方法,因为他必须收集每张地图上存在的所有硬币(⍟),并收集他得到的所有硬币。通往下一个世界的门票。 在每个世界中,除了...
> mix deps.getnewb |> iex -S mix "use it Padawan"newb |> AST quote do - discover code patternsnewb |> require Loggernewb |> Logger.debug("debug message: Make it meaningful")newb |> alias :dbg, as: Dbg...
该模块还出现在web-padawan / awesome-lit-html中。 确保检查回购以获取受lit-html启发的令人敬畏的事情。 :thumbs_up: :hundred_points: 目录特征前提条件使用模板文字编写HTML时启用语法突出显示Visual Studio程...
Web开发人员全栈JS,对UX设计充满热情 :artist_palette:介绍 :studio_microphone: :rocket: Padawan Web开发人员,喜欢设计和开发各种Web项目! 主要研究一种奇怪的语言,即Javascript,最近又发现与Typescript...
vimrc 这是我的.vimrc。 根据我如何使用vim,这是一项正在进行的工作。 使用风险自负。 使用和修改您的心脏内容。 功劳归于原始创作者。 我只是一个谦虚的padawan。