2019年1月22日 星期二

APCS b966: 第3題 線段覆蓋長度

原題請見 APCS大學程式設計先修檢測 (2016/03/05)
以下為通過高中生程式解題系統 AC (Accepted) 的 C 語言程式參考解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <stdio.h>
#include <stdlib.h>

#define MAX 10000
int main()
{
    int n=0;
    signed int line[MAX][2]={{0}};

    while(scanf(" %d",&n)!=EOF){

    for(int i=0 ; i<n ; i++)
    {
        scanf(" %d %d",&line[i][0],&line[i][1]);

        for(int j=0; j<i ; j++)
        {
            if(line[i][0]<line[j][0])
            {
            int tmp[2]={line[i][0],line[i][1]};
            for(int k=i; k>j ; --k)
            {
                line[k][0] = line[k-1][0];
                line[k][1] = line[k-1][1];
            }
            line[j][0]=tmp[0];
            line[j][1]=tmp[1];
            break;
            }
        }
    }

    int start=line[0][0], end=line[0][1];
    int length=0;
    for(int i=1; i<n ; i++)
    {
        if(line[i][0]<=end)
        {
            if(line[i][1]>end)
                end = line[i][1];
        }
     else{
        length += (end-start);
        start=line[i][0];
        end=line[i][1];
        }
    }

    length += (end-start);
    printf("%d\n",length);
    }
    return 0;
}
標籤：

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)