此題在高中生程式解題系統的題號為:b966: 第 3 題 線段覆蓋長度。
筆者的解題作法:
方法一(C程式碼):
此方法有可能會得到70分,無法得到100分,但高中生程式解題系統讓筆者過了!?
用一個布林陣列 p 來記錄那些地方有被畫線,以及紀錄所有線段上的最小值 min 與最大值 max,接著用迴圈從 min 到 max 計算有多少地方被畫線,見下圖。
方法二(C++程式碼):
使用一個結構陣列 struct Point p 來記錄所有線段,並將此結構陣列由小排到大(見下圖),
接著在判斷目前的線段是否有所覆蓋下一個線段,而這有三種狀況:
1. 完全覆蓋下一線段,此情況直接繼續下一線段的判斷。
2. 部分覆蓋,將目前線段的結尾更新為下一線段的結尾。
3. 沒有覆蓋下一線段,計算目前連線起來的線段長度,並加總到總長度 cnt 。
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 | #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <string.h> #define NUM 10000000 bool p[NUM]; int main(void) { int n; while(scanf("%d",&n) != EOF ) { // 清除標記 memset(p,0,sizeof(char)); int a, b, min = NUM, max = -1; for(int i = 0; i < n; i++) { scanf("%d%d", &a, &b); if(min > a) min = a; if(max < b) max = b; for(int j = a; j < b; j++) p[j] = 1; // 畫線標記 } // 計算長度 int cnt = 0; for(int i = min; i < max; i++) if(p[i] == 1) cnt++; printf("%d\n", cnt); } return 0; } |
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 54 | #include <iostream> #include <algorithm> using namespace std; #define NUM 10000 struct Point { int s; int e; }; Point p[NUM]; int cmp(Point p1, Point p2) { if(p1.s == p2.s) return p2.e > p1.e; else return p2.s > p1.s; } int main(void) { int n; while (cin >> n) { for(int i = 0; i < n; i++) cin >> p[i].s >> p[i].e; sort(p, p + n, cmp); // 將所有線段由小排到大 int cnt = 0, s, e; for(int i = 0; i < n; i++) { s = p[i].s; e = p[i].e; while(i + 1 < n && p[i+1].s < e) // 是否有覆蓋到下一線段 { if(p[i+1].e < e) i++; // 覆蓋到下一線段的全部 else { e = p[i+1].e; // 有部分覆蓋到下一線段,以下一線段的結尾 e 當成目前的結尾。 i++; } } cnt += e - s; // 計算線段長度 } cout << cnt << endl; } return 0; } |
沒有留言:
張貼留言