進階班選幹題解

---

ZJ c575: APCS 2017-0304-4基地台

題目簡介

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

---

想法

• 先把服務台座標
  $sort$ 過，後續處理較輕鬆
• 每種直徑最少需要幾個基地台
• 基地台個數 <=k 且直徑最小
• 暴搜直徑真好寫 使用二分搜找直徑 –->
  $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;
}