xindoo is
always here

codeforces 302 B. Eugeny and Play List


题目链接

有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;

}
打赏
未经允许不得转载:XINDOO » codeforces 302 B. Eugeny and Play List
分享到: 更多 (0)

评论 抢沙发

xindoo

联系我联系我们

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏