Description
Eugeny loves listening to music. He hasnsongs in his play list. We know that song numberihas the duration oftiminutes.
Eugeny listens to each song, perhaps more than once. He listens to song numbericitimes. Eugeny's
play list is organized as follows: first song number1playsc1times, then song number2playsc2times,...,
in the end the song numbernplayscntimes.
Eugeny took a piece of paper and wrote outmmoments of time when he liked a song. Now for each such moment he wants to know the number of the song that played at that moment. The momentxmeans
that Eugeny wants to know which song was playing during thex-th minute of his listening to the play list.
Help Eugeny and calculate the required numbers of songs.
Input
The first line contains two integersn,m(1 ≤ n, m ≤ 105).
The nextnlines contain pairs of integers. Thei-th line contains integersci, ti(1 ≤ ci, ti ≤ 109)—
the description of the play list. It is guaranteed that the play list's total duration doesn't exceed109.
The next line containsmpositive integersv1, v2, ..., vm,
that describe the moments Eugeny has written out. It is guaranteed that there isn't such moment of timevi, when the music doesn't play any longer. It is
guaranteed thatvi < vi + 1(i < m).
The moment of timevimeans that Eugeny wants to know which song was playing during thevi-th
munite from the start of listening to the playlist.
Output
Printmintegers — thei-th number must equal the number of the song that was playing during thevi-th
minute after Eugeny started listening to the play list.
题意: 给出n首歌, m个时间点
接下来的n行, 每行两个数, 分别代表该首歌要循环放几次, 一次放多久
然后最后一行输入m个时间点, 求在这m个时间点里, 每个时间点是在放哪首歌?
做法: 直接for循环了, 也有二分法做法
AC代码:
#include<stdio.h>
int n, m;
int songList[311111];
int time[311111];
int main() {
while(scanf("%d %d", &n, &m) != EOF) {
songList[0] = 0;
for(int i = 1; i <= n; i++) {
int v, c;
scanf("%d %d", &v, &c);
songList[i] = v * c + songList[i-1];
}
for(int i = 0; i < m; i++)
scanf("%d", &time[i]);
int begin = 1;
for(int i = 0; i < m; i++) {
for(int j = begin; j <= n; j++) {
if(time[i] > songList[j-1] && time[i] <= songList[j]) {
printf("%d\n", j);
begin = j;
break;
}
}
}
}
return 0;
}
分享到:
相关推荐
安国ALCOR MP_v13.10.28.01.C
M3257ENAA_v13.10.17.04.exe
DandyMP3Player(迷你MP3播放器)是一款精美小巧的MP3音乐播放器,界面简洁、美观,功能齐全,使用方便,麻雀虽小...DandyMP3Player(迷你MP3播放器) v13.10.28版本更新: 1,去除自动更新模块。 2,添加合作项目。
DandyHRSystem(人事管理系统)是一款简单的人事信息管理软件,可对人事信息进行相关的录入与查询。 DandyHRSystem(人事管理系统)... v13.10.19更新: 1,添加合作项目. 2,去除自动更新.
mtk3360方案,大众通用 APP:DZ_13.12.16_16346 MCU:43.6.1.25_13.10.29
gitlab rpm 安装包
安国 AU6989SNHL 量产工具
gitlab清华站下载的,社区版
IPC_AX_2.4.13.10.exe
10053 工程数学13.10.doc
08241 计算机控制系统13.10.doc
02286电力电子技术13.10.doc
08239工业过程与过程控制13.10.doc
j5create JUD200/JUD500扩展坞驱动13.10.0522.3185版For WinXP-32/WinXP-64/Vista-32/Vista-64/Win7-32/Win7-64/Win8-32/Win8-64(2013年6月9日发布) j5create是美国一家专注于简化用户电脑操作的外设厂商,每年...
DandySnap(仿QQ截图工具)是一款高仿QQ截图的软件,可拖动鼠标进行截图并可对截图进行编辑保存等相关操作. DandySnap(仿QQ截图工具) v13.10.18版本更新: 1,添加合作项目 2,去除自动更新
13.10.17.04版本慧荣的黑片专用,如果是正片,请下载正片专用工具。 支持芯片无忧检测主控是SM3255AB/3257AA/sm3257enaa芯片量产修复使用,默认无设定密码。 可以高格/低级格式化U盘。支持设置读写时钟频率,最多...
资源分类:Python库 所属语言:Python 资源全名:phanterpwa-13.10.4-py3-none-any.whl 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
金士顿8G g3 SM3257ENAA芯片量产_v13.10.11.05让你的U盘好起来,不能用的就能用了,很好用,网上专用的不能量产的,来试试这个吧
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 ...
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 ...