题解 | 音符

//我的做法和上面那位大佬一样都是先用了提取前n个音符总拍数的数组，做了数据预处理

#include <stdio.h>
#include <stdlib.h>

//提前声明一下函数search
int search(int *p, int p_size, int k);

int main() {
    //读入数据
    int n,q;
    scanf("%d %d\n",&n,&q);
    int *b = (int *)malloc(sizeof(int) * n);
    int *t = (int *)malloc(sizeof(int) * q);
    if(b == NULL || t == NULL){
        printf("Failed Malloc!\n");
        return -1;
    }
    for(int i = 0; i < n; i ++){
        scanf("%d",b + i);
    }
    for(int i = 0; i < q; i ++){
        scanf("%d",t + i);
    }
    //perfix_sum数组记录前i个音符的总拍数
    int *perfix_sum = (int *)malloc(sizeof(int) * (n + 1));
    if(perfix_sum == NULL){
        printf("Failed malloc!\n");
        return -1;
    }
    //前0个音符一共有0拍
    perfix_sum[0] = 0;
    for(int i = 1; i < n + 1; i ++){
        perfix_sum[i] = perfix_sum[i - 1] + b[i - 1];
    }
    
    //对q个输入的时刻进行处理
    for(int i = 0; i < q; i ++){
        int num = search(perfix_sum, n + 1, t[i]);
        printf("%d\n", num);
    }
    
    //释放空间
    free(b);
    free(t);
    free(perfix_sum);
    return 0;
}


//要找第t时刻在弹奏第几个音符，只需要找到第一个大于t的perfix_sum[i]即可，i即为所求的音符序号
//定义在排序好的数组中找到第一个大于键值的位置的函数

int search(int *p, int p_size, int k){
    for(int i = 0; i < p_size; i ++){
        if(p[i] > k){
            return i;
        }
    }
    return -1;
}