题目链接
有n首歌，编号从1到n，每首歌播放时间为t，播放次数为c，n首歌按次序播放，有m个询问，输出第v分钟正在播放的歌曲编号。
很简单的二分查找，直接贴代码。
//2013-05-23-20.26
#include <stdio.h>
#include <string.h>
using namespace std;
const int maxn = 100005;
int sum[maxn];
int binary_search(int l, int r, int v)
{
int mid = (l+r)>>1;
if (l == r)
return l;
if (v > sum[mid])
return binary_search(mid+1, r, v);
else
return binary_search(l, mid, v);
}
int main()
{
int n, m, c, t, v;
//freopen("data.txt", "r", stdin);
while (scanf("%d%d", &n, &m) != EOF)
{
memset(sum, 0, sizeof(sum));
for (int i = 1; i <= n; i++)
{
scanf("%d %d", &c, &t);
sum[i] = sum[i-1] + c*t;
}
while (m--)
{
scanf("%d", &v);
printf("%d\n", binary_search(1, n, v));
}
}
return 0;
}
