# APCS程式設計實作題
**第1題 成績指標**

:::success

:::

#include <iostream>
#include <algorithm>//for sort
#define     MAX     20+5//最大的學生數
using namespace std;

int scores[MAX];    //儲存所有輸入學生的分數
int main()
{
    int people;  //儲存輸入的學生人數(第一行輸入資料)
    cin>>people; //輸入學生人數

    //連續讀取 n個學生的分數(第二行)
    //分別儲存 scores 陣列
    for(int i=0; i<people; i++)
    {    //將讀取的資料存入 scores[i]
        //第i個學生人數
        cin>>scores[i];
    }
    //將分數由小到大排序
    sort(scores, scores+people);
    //第一行由小而大 印出所有成績,兩數字之間以一個空白格隔開
    int firat = 1;
    for(int i=0; i<people; i++)
    {
        if(firat)
        {
            cout<<scores[i];
            firat = 0;
        }
        else
        {
            cout<<" "<<scores[i];
        }
    }
    cout<<"\n";
    //代表不及格最高分
    //-1:代表沒有不及格的
    int b60 = -1;
    for(int i=0; i<people; i++)
    {
        if(scores[i]<60)
            b60=scores[i];
    }
    if(b60==-1)
        cout<<"best case\n";
    else cout<<b60<<"\n";

    //代表不及格最高分
    //-1:代表沒有不及格的
     b60 = -1;
    for(int i=people-1; i>=0; i--)
    {
        if(scores[i]>=60)
            b60=scores[i];
    }
    if(b60==-1)
        cout<<"worst case\n";
    else cout<<b60<<"\n";



    return 0;
}

:::info
**驗證1**
:::
:::warning
**驗證2**
:::

#include <iostream>
#include <algorithm>//for sort
#define     MAX     20+5//最大的學生數
using namespace std;

int scores[MAX];    //儲存所有輸入學生的分數
#define LOCAL     //本機電腦測試
#include<cstdio>
int main()
{
#ifdef LOCAL
freopen("data.inp", "r", stdin);
freopen("data.out", "w", stdout);
#endif // LOCAL
        int people;  //儲存輸入的學生人數(第一行輸入資料)
        while(cin>>people)//輸入學生人數
        {
            //連續讀取 n個學生的分數(第二行)
        //分別儲存 scores 陣列
        for(int i=0; i<people; i++)
        {    //將讀取的資料存入 scores[i]
            //第i個學生人數
            cin>>scores[i];
        }
        //將分數由小到大排序
        sort(scores, scores+people);
        //第一行由小而大 印出所有成績,兩數字之間以一個空白格隔開
        int firat = 1;
        for(int i=0; i<people; i++)
        {
            if(firat)
            {
                cout<<scores[i];
                firat = 0;
            }
            else
            {
                cout<<" "<<scores[i];
            }
        }
        cout<<"\n";
        //代表不及格最高分
        //-1:代表沒有不及格的
        int b60 = -1;
        for(int i=0; i<people; i++)
        {
            if(scores[i]<60)
                b60=scores[i];
        }
        if(b60==-1)
            cout<<"best case\n";
        else cout<<b60<<"\n";

        //代表不及格最高分
        //-1:代表沒有不及格的
         b60 = -1;
        for(int i=people-1; i>=0; i--)
        {
            if(scores[i]>=60)
                b60=scores[i];
        }
        if(b60==-1)
            cout<<"worst case\n";
        else cout<<b60<<"\n";


    }


    return 0;
}


第三題
:::success
:::
解法1(使用陣列，較差)

#include <iostream>
#include <cstring>  // for memset()
#include <cstdio>

#define MAXM 10000000+10    // 最大線段座標

using namespace std;

int lines[MAXM];    // 儲存所有座標

int main(){

    int n;  // 儲存輸入的線段數 (第一行)

    while(cin>>n){
        memset(lines,0,sizeof(lines));    // 將lines的所有元素設為0

        int st,ed;  // 起點,終點
        for(int i=0;i<n;i++){   // 讀取n筆線段資料    (第二行~結束)
            cin>>st>>ed;
            for(int j=st;j<ed;j++){   // 將起點到終點之間的元素設為1
                lines[j]=1;
            }
        }

        int len=0;  // line長度
        for(int i=0;i<MAXM;i++){    // 計算len (lines內元素總和)
            len+=lines[i];
        }
        cout<<len<<"\n";   // 輸出
    }
    return 0;
}

解法2(使用自訂結構，較佳)

#include <iostream>
#include <algorithm>  //for sort()
#include <cstdio> //for freopen()
#define     MAXN    10000+10    //最多line數
#define     LOCAL     // for local testing

using namespace std;

//定義線段結構
typedef struct _line
{
    int start;  //線段起點
    int end;     //線段終點
}LINE;          //自訂struct _line的資料型態為LINE

//宣告儲存所有線段的LINE結構陣列
LINE lines[MAXN];

//起點小的排前面
//起點相同終點小的排前面

int cmp(LINE p, LINE q)
{
    if(p.start==q.start) return p.end<q.end;
        else return p.start<q.start;
}

int main()
{
#ifdef LOCAL

freopen("data3.inp","r", stdin);
freopen("data3.out","w", stdout);

#endif //LOCAL

    int n;      //輸入的線段數
    while(cin>>n)
    {
        //將n筆線段起點與終點 存入
        for(int i=0; i<n; i++)
        {
            //第i筆線段的起點與終點存入
            cin>>lines[i].start>>lines[i].end;
        }
        //有小到大排序(自訂排序準則)
        sort(lines, lines+n, cmp);

        //計算線段長度
        int st, ed, lens = 0;
        for(int i=0; i<n; i++)
        {
            st = lines[i].start;   //第i個線段的起點
            ed = lines[i].end;      //第i個線段的終點
            //判斷下一個線段(i+1)是否與目前的線段(i)重疊
            while((i+1)<n && lines[i+1].start<ed)
            {
                //完全重疊
                if(lines[i+1].end<=ed) i++;  //移到下一個線段
                else  //部分重疊
                {
                    ed = lines[i+1].end;  //將下一個線段的終點設為目前的終點
                    i++; //移到下一個線段
                }
            }
            //加入線段長度
            lens+=ed-st;
        }
        //輸出結果
        cout<<lens<<"\n";
    }
    return 0;
}