[USACO 2009 Dec S]Music Notes

简介: [USACO 2009 Dec S]Music Notes

题目: [USACO 2009 Dec S]Music Notes ,哈哈,我们今天来看一道有二分思想的题嘛,这是选自USACO上的一道题,好了,我们一起来看看题意吧:

题目描述是复制的,可能有部分显示不对,我就把题目链接放下面!

题目链接: [USACO 2009 Dec S]Music Notes

题目描述

FJ is going to teach his cows how to play a song. The song consists of N (1 <= N <= 50,000) notes, and the i-th note lasts for Bi (1 <= Bi <= 10,000) beats (thus no song is longer than 500,000,000 beats). The cows will begin playing the song at time 0; thus, they will play note 1 from time 0 through just before time B1, note 2 from time B1 through just before time B1 + B2, etc. However, recently the cows have lost interest in the song, as they feel that it is too long and boring. Thus, to make sure his cows are paying attention, he asks them Q (1 <= Q <= 50,000) questions of the form, "In the interval from time T through just before time T+1, which note should you be playing?" The cows need your help to answer these questions which are supplied as Ti (0 <= Ti <= end_of_song).

输入描述

  • Line 1: Two space-separated integers: N and Q
  • Lines 2…N+1: Line i+1 contains the single integer: Bi
  • Lines N+2…N+Q+1: Line N+i+1 contains a single integer: Ti

输出描述

  • Lines 1…Q: Line i of the output contains the result of query i as a single integer.

示例1

输入

3 5

2

1

3

2

3

4

0

1

输出

2

3

3

1

1

思路:

采用前缀和与二分的思想,很快就解决了

我们来看看成功AC的代码吧:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,q;
int a[1000010];
int sum[1000010];//存放前缀和的
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
    }
    while(q--){
        int x;  cin>>x;
        int ans=upper_bound(sum+1,sum+n+1,x)-sum;//这里减掉起始位置就是元素的下标了
        cout<<ans<<"\n";
    }
    return 0;
}


相关文章
[USACO 2021.02 Feb]Problem 1. Year of the Cow
[USACO 2021.02 Feb]Problem 1. Year of the Cow
|
C++
hdoj 4288coder & cf 85d Sum of Medians
这两个题目是一样的,大概题意是有3个操作 add x, 在集合中加入x, del x 是删除x, sum 是求出由小到大排序后所有下标mod5等于3的数的和。
33 0
|
存储
PAT (Advanced Level) Practice 1011 World Cup Betting (20 分)
PAT (Advanced Level) Practice 1011 World Cup Betting (20 分)
84 0
Data Structures and Algorithms (English) - 7-10 Saving James Bond - Easy Version(25 分)
Data Structures and Algorithms (English) - 7-10 Saving James Bond - Easy Version(25 分)
91 0
|
消息中间件 数据建模
题解 P1339 【[USACO09OCT]热浪Heat Wave】
题目链接 这道题纯属是一个裸的SPFA;建议先把模板AC之后再做。只需要做一些手脚,就是在加边的时候加一个双向边就好。然后再第一次加点的时候看不懂模板的出门左转度娘。推荐下面一片讲解:友链所以说,直接上代码。
1142 0
SAP HUM 如何看一个HU的Output?
SAP HUM 如何看一个HU的Output? HU03, input the HU number,   Execute,   ...
1031 0