---
# System prepended metadata

title: Java ArrayList搭配物件導向題型練習
tags: [apcs, 歷屆練習, 自主學習, 解題筆記]

---

###### tags: `apcs` `解題筆記` `歷屆練習` `自主學習`
Java ArrayList搭配物件導向題型練習
===
[TOC]

運用Java的類別來解題，運用介面Comparable可以時做二維陣列的sort；樹狀圖題目也是用類別儲存節點來實作，非常活用。
:::info
物件導向算是最慢的解題技巧之一，只是比較方便，不是最佳解法。
:::
```java=
//線段覆蓋長度題目
class A implements Comparable<A>{
	int start,end;
	public A(int start,int end){
		this.start = start;
		this.end = end;
	}
	public int compareTo(A o) {
		return start - o.start;//將start由小排到大
	}
}
//樹狀圖的節點就是用類別來實作
class E{
	int value,layers;
	E parent;
	E(int value,int layers,E parent){
		this.layers = layers;
		this.parent = parent;
		this.value = value;
	}
	ArrayList<E> children = new ArrayList<>();
}
```
## [歷屆：線段覆蓋長度(物件導向排序版解題)](https://zerojudge.tw/ShowProblem?problemid=b966)
![](https://i.imgur.com/Vf352vM.jpg)
這題其實用一維陣列就可以解開，不過也很適合拿來練習物件導向排序。
```java=
import static java.lang.System.*;
import static java.lang.Integer.*;
import java.util.*;
import java.io.*;
public class zj_f855 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(in));
		int n = parseInt(br.readLine());
		long ans = 0;
		A[] list = new A[n];
		//輸入
		for(int i = 0;i < n;i++) {
			String[] d = br.readLine().split(" ");
			list[i] = new A(parseInt(d[0]),parseInt(d[1]));
		}
		Arrays.sort(list);
		//Na,Nb=比對值左右
		int Na = list[0].start,Nb = list[0].end;
		ans += Nb - Na;
		for(int i = 1;i < n;i++) {
			//Ta,Tb=現在比對值左右
			int Ta = list[i].start,Tb = list[i].end;
			//不覆蓋:計算後刷新比對值
			if(Ta > Nb) {
				ans += Tb - Ta;
				Na = Ta;
				Nb = Tb;
			}
			//覆蓋:計算後刷新比對值的尾
			else if(Tb > Nb) {
				ans += Tb - Nb;
				Nb = Tb;
			}
		}
		out.println(ans);
	}
}
class A implements Comparable<A>{
	int start,end;
	public A(int start,int end){
		this.start = start;
		this.end = end;
	}
	//將起始值由小排到大
	public int compareTo(A o) {
		return start - o.start;
	}
	
}
```
## [歷屆：物品堆疊](https://zerojudge.tw/ShowProblem?problemid=c471)
![](https://i.imgur.com/AarPcvy.jpg)
透過排序實現規律的數學交叉運算
```java=
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;

public class zj_c417 {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		Box[] box = new Box[n];
		for(int i = 0;i < n;i++)
			box[i] = new Box();
		//輸入
		String[] d = br.readLine().split(" ");
		String[] t = br.readLine().split(" ");
		for(int i = 0;i < n;i++) {
			box[i].w = Integer.parseInt(d[i]);
			box[i].f = Integer.parseInt(t[i]);
		}
		//排序
		Arrays.sort(box);
		long sum = 0,ans = 0;
		//加起來
		for(int i = 0;i < n-1;i++) {
			sum += box[i].w;
			ans += box[i+1].f * sum;
		}
		System.out.println(ans);
	}

}
//類別存重量、次數，用w*o.f-o.w*f排序
class Box implements Comparable<Box>{
	int w,f;
	public int compareTo(Box o) {
		return w * o.f - o.w*f;
	}
}
```






