现在的位置: 首页 > 综合 > 正文

BNU寒假弱校联盟C.Shorter Musical Notes(upper_bound的使用)

2018年04月28日 ⁄ 综合 ⁄ 共 1808字 ⁄ 字号 评论关闭

C. Shorter Musical Notes

Time Limit: 1000ms
Memory Limit: 65536KB

64-bit integer IO format: %lld     
Java class name: Main

 FJ is going to teach his cows how to play a song. The song consists of N (1 <= N <= 10,000) notes, and the i-th note lasts for B_i (1<= B_i <= 120) beats (thus no song is longer than 1,200,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 B_1, note 2 from time B_1 through just before time B_1 + B_2, 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
T_i (0 <= T_i <= end_of_song).
 
Consider this song with three notes of durations 2, 1, and 3 beats:
 
Beat:   0    1    2    3    4    5    6    ...
        |----|----|----|----|----|----|--- ...
        1111111111     :              :
                  22222:              :
                       333333333333333:
 
Here is a set of five queries along with the resulting answer:
 
   Query    Note
     2        2
     3        3
     4        3
     0        1
     1        1
 

Input

* Line 1: Two space-separated integers: N and Q
 
* Lines 2..N+1: Line i+1 contains the single integer: B_i
 
* Lines N+2..N+Q+1: Line N+i+1 contains a single integer: T_i
 

Output

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

Sample Input

3 5
2
1
3
2
3
4
0
1

Sample Output

2
3
3
1
1

解题思路:

题目的意思就是先输入n个数字,然后q个询问,问每次询问的数字是1->x个数字中的哪一个了。

比如说,2 1 3,那么实际就是1 1 2 3 3 3 。。。怎么询问,你就怎么查数就好了。

upper_bound(x)是返回大于x的第一个元素。。。

代码:

# include<cstdio>
# include<iostream>
# include<algorithm>

using namespace std;

# define MAX 10000+4

int a[MAX];
int sum[MAX];

int main(void)
{
    int n,q;
    cin>>n>>q;
        for ( int i = 1;i <= n;i++ )
        {
            scanf("%d",&a[i]);
        }
        for ( int i = 1;i <= n;i++ )
        {
            sum[i]=sum[i-1]+a[i];
        }
        for ( int i = 0;i < q;i++ )
        {
            int temp;
            scanf("%d",&temp);
            int p = upper_bound(sum+1,sum+n+1,temp)-sum;
            printf("%d\n",p);
        }
        
    return 0;
}

抱歉!评论已关闭.