# 進階班選幹題解
---
## ZJ c575: APCS 2017-0304-4基地台
### 題目簡介

給定數個服務台的一維座標 `arr[n]`及基地台個數 `k`，輸出基地台最小直徑為何？
(所有基地台服務直徑相等)

---
### 想法

- 先把服務台座標 $sort$ 過，後續處理較輕鬆
- 每種直徑最少需要幾個基地台
- 基地台個數 `<=k` 且直徑最小
- <font color="#9A9898">~~*暴搜直徑真好寫*~~</font> 使用二分搜找直徑 ---> $O(n^2)$ -> $O(nlgn)$
---
### 程式碼

    sort(v.begin(), v.end());
    while (dl != dr - 1) {
        int x, tmp = v[0];
        for (x = 0; x < p; x++) {
            tmp += dm;
            if (tmp >= v[v.size() - 1]) 
                {ans = dm, dr = dm; break;}
            tmp = *upper_bound(v.begin(), v.end(), tmp);
        }
        if (x == p) dl = dm;
        dm = (dl + dr) >> 1;
        if (dm == 1) dl = 0;
    }
    cout << ans << '\n';
    return 0;
}

---
## DJ a139: 二維偏序問題
### 題目簡介

給定二維座標點集 $P$，依序對第 $i$ 個點 $(x_i, y_i)$ 輸出 $P$ 中 $x_i<x_j$ 且 $y_i<y_j$ 之 $(x_j,y_j)$ 個數。

---
### 想法

- 先對第一維座標 $sort$ 過後，對第二維座標做順序數對
- 因為 $sort$ 會讓點順序跑掉，所以刻一個 $struct$ 存位置
- 注意第一維或第二維座標相等的點不能算進去
---
### 程式碼

struct dot {
	int x, y, pos;
	bool operator<(dot d) {return ((x < d.x) || (x == d.x && y < d.y) 
                                ||(x == d.x && y == d.y && pos < d.pos));}
};
void merge_sort(vector<dot>& v, vector<int>& time) {
	if (v.size() != 1) {
		merge_sort(left, time), merge_sort(right, time);
		size_t l = 0, r = 0, x = 0;
		while (l != left.size() && r != right.size()) {
			if (left[l].y > right[r].y || 
                          (left[l].y == right[r].y && left[l].x < right[r].x)) {
				v[x] = left[l], l++;
				time[v[x].pos] += r;
			}
			else 
				v[x] = right[r], r++;
			x++;
		}
		while (l != left.size()) v[x] = left[l], l++, 
                                        time[v[x].pos] += r, x++;
		while (r != right.size()) v[x] = right[r], r++, x++;
	}
	else return;
}
int main(){
    for (int x = 0; x < n; x++) cin>>v[x].x>>v[x].y,v[x].pos = x;
    sort(v.begin(), v.end());
    vector<int> time(n, 0);
    for (int x = n - 1; x >= 0; x--) {
        if (tmp != v[x].x) tmp = v[x].x, cnt = 0;
        else cnt++, time[v[x].pos] -= cnt;
    }
    merge_sort(v, time);
    for (auto&i : time) cout << i << '\n';
    return 0;
}