###### tags: `計概詳解`
# 書本的位置(Public)
圖書館有 n 排書架，第 1 排有 a1 本書，編號依次為 1, 2,..., a1 ；
第 2 排有 a2 本書，編號依次為 a1+1, a1+2,... ,a1+a2；
依次類推，最後一本書的編號為 a1+a2+...+an。

現已知書本編號 b1,... , bm ，要找出這些書本所在的排數。

## 解題思維
請參考老師的解說影片：i-learning/開始上課/2021-課程內容/N13-單元四作業講解

### 解法1：暴力破解法
建表<code>table[]</code>紀錄每一本書在第幾排，取得書本編號b之後，直接查表<code>table[b]</code>就知道書在第幾排。
https://youtu.be/msZnK_QbB-0
### 程式碼1

#include <stdio.h>

#define N 100000 //假設書本不超過100000萬本

int main()
{
    int table[N];//建表
    int n, a, m, b;
    int cnt = 0;//表示正在處理編號cnt的書。
    
    scanf("%d", &n);//讀取 n(圖書館有n排書架)
    for (int i=1; i<=n; i++){//重複n次
        scanf("%d", &a);//讀取一個a
        for (int j=0; j<a; j++){//連續a本書都設定成第i排
            table[++cnt] = i;
        }
    }
	
    scanf("%d", &m);//讀取m
    for (int i=0; i<m; i++){//重複處理m本書
        scanf("%d", &b);//讀取一個b
        printf("%d\n", table[b]);//輸出查表結果
    }
    return 0;
}

### 解法2：線性解
記每一排最後一本書的編號，找第一個超過書本b的那一排。
https://youtu.be/gPcD6w4EGm8
### 程式碼2

/*線性解*/
#include <stdio.h>

int main()
{
    int n, m, k;
    scanf("%d", &n);
    int r[n+1];
    r[0] = 0;
    for (int i=1; i<=n; i++){
        scanf("%d", &k);
        r[i] = r[i-1] + k;
    }
    scanf("%d", &m);
    for (int i=0; i<m; i++){
        scanf("%d", &k);
        int row=1;
        while(r[row] < k) row++;
        printf("%d\n", row);
    }
    return 0;
}

### 解法3：二分搜尋法
記每一排最後一本書的編號，找第一個超過書本b的那一排。
使用二分搜尋法來找第幾排，可以加快運算速度。
https://youtu.be/hGdIvob4xjg

### 程式碼3

/*二分搜尋法*/
#include <stdio.h>

int bsearch(int r[], int start, int end, int k);
int main()
{
    int n, m, k;
    scanf("%d", &n);
    int r[n+1];
    r[0] = 0;
    for (int i=1; i<=n; i++){
        scanf("%d", &k);
        r[i] = r[i-1] + k;
    }
    scanf("%d", &m);
    for (int i=0; i<m; i++){
        scanf("%d", &k);
        printf("%d\n", bsearch(r, 1, n, k));
    }
    return 0;
}

int bsearch(int r[], int start, int end, int k)
{
    int mid=(start+end)/2;
    if (r[mid]>=k && r[mid-1]<k) return mid;
    if (r[mid] < k) return bsearch(r, mid+1, end, k);
    return bsearch(r, start, mid-1, k);
}