【程式解題】 APCS - 2016/3/5 第三題：線段覆蓋長度 C解法(逐行註解)

題目請點此

評分結果：AC (15ms, 4MB)

解題思路：製造布林陣列，填格子式解法。

備註：使用初始化的動態陣列。

逐行註解的程式碼：

#include <stdio.h>

#include <stdlib.h>

int main(){

long i,j;//loop

int n;//輸入資料有幾筆 

int L[10000]={0};//輸入線段左端點 

int R[10000]={0}; //輸入線段右端點 

int *line;//布林動態陣列

int max=0;//右端點最大值

int sum=0;//長度 

scanf("%d",&n);//輸入 

for(i=0;i<n;++i){

scanf("%d%d",&L[i],&R[i]);//輸入 

}

for(i=0;i<n;++i){

if(R[i]>max) max=R[i];//取右端點最大值

}

line=(int*)calloc(max, sizeof(int));//動態陣列line，初始化為0

//填格子  

        for(i=0;i<n;++i){

for(j=L[i];j<R[i];++j) 

line[j]=1;//在線段的覆蓋範圍內，就改成 1

}

for(i=0;i<max;++i){//max用在這，避免超時

sum+=line[i];//把覆蓋的長度加總

}

free (line);//釋放記憶體空間

printf("%d\n",sum);//output

return 0;

}