校門外的樹
題目來源：《NOIP2005普及組》
時間限制：1000ms 記憶體限制：128mb
題目描述
某校大門外長度為L的馬路上有一排樹，每兩棵相鄰的樹之間的間隔都是1米，
我們可以把馬路看成一個數軸，馬路的一端在數軸0的位置，另一端在L的位置；數軸上的每個整數點，即0，1，2，……，L，都種有一棵樹，
由于馬路上有一些區域要用來建地鐵，
這些區域用它們在數軸上的起始點和終止點表示，
已知任一區域的起始點和終止點的坐標都是整數，區域之間可能有重合的部分，
現在要把這些區域中的樹（包括區域端點處的兩棵樹）移走，
你的任務是計算將這些樹都移走后，馬路上還有多少棵樹，
輸入格式
輸入檔案的第一行有兩個整數L和M，L代表馬路的長度，M代表區域的數目，L和M之間用一個空格隔開，
接下來的M行每行包含兩個不同的整數，用一個空格隔開，表示一個區域的起始點和終止點的坐標，
輸出格式
輸出檔案包括一行，這一行只包含一個整數，表示馬路上剩余的樹的數目，
資料范圍
\(1≤L≤10000\),
\(1≤M≤100\)
樣例輸入
500 3
150 300
100 200
470 471
樣例輸出
298
解題思路1：暴力破解（模擬）
1.宣告一個\(boolean\)陣列\(tree[]\)表示馬路，長度為\(L+1\)，其中的每個元素代表樹的狀態:\(\begin{cases}true: 有樹 \\false：沒有樹\end{cases}\)
2.遍歷給定的每一個區域，將區域內的樹移走，即：\(tree[i] = false\)
3.統計移走所有給定區域的樹之后剩余的樹，即：\(tree\)陣列內有多少值為\(true\)的項，
解題代碼1-Java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int l = input.nextInt();
int m = input.nextInt();
boolean[] tree = new boolean[l + 1];
for (int i = 0; i <= l; i++) {
tree[i] = true;
}
for (int i = 0; i < m; i++) {
int start = input.nextInt();
int end = input.nextInt();
for (int j = start; j <= end; j++) {
tree[j] = false;
}
}
input.close();
int res = 0;
for (int i = 0; i <= l; i++) {
res += (tree[i] ? 1 : 0);
}
System.out.println(res);
}
}
解題思路2：區間合并
1.將要砍掉樹的區間合并在一起，合并后的區間沒有重合部分，例如：[1-3]和[3-5] 合并成 [1-5]，
2.樹的總數 - 合并后所有區間覆寫的點數 = 剩余樹的數量，
區間合并：
1.將區間按左端點升序排序，
2.從第一個區間開始，如果該區間的右端點大于后面相鄰區間的左端點，當前區間右端點更新為：該區間右端點和相鄰區間右端點最大值，直到不能繼續合并，然后開始后面區間合并，
解題代碼2-Java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int l = input.nextInt();
int m = input.nextInt();
int[][] road = new int[m][2];
for (int i = 0; i < m; i++) {
road[i][0] = input.nextInt();
road[i][1] = input.nextInt();
}
input.close();
Arrays.sort(road, new Comparator<int[]>() { //按照二維陣列的首項排序，首項相同按第二項排序
@Override
public int compare(int[] o1, int[] o2) {
if (o1[0] == o2[0])
return o1[1] - o2[1];
return o1[0] - o2[0];
}
});
int res = l + 1;
int start = road[0][0], end = road[0][1];
for (int i = 1; i < m; i++) {
if (end >= road[i][0]) {
end = Math.max(end, road[i][1]);
} else {
res -= end - start + 1;
start = road[i][0];
end = road[i][1];
}
}
res -= end - start + 1;
System.out.println(res);
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/250078.html
標籤：其他
上一篇：一條命令生成msyql資料庫的REST API的xmysql
下一篇：三、k8s 核心功能