CodeForces 607A - Chain Reaction
題意:
在同一橫軸上有一些信標，功率b的信標a啟動後會將左邊距離b以內的信標都摧毀，現在給你N個信標的座標跟功率，並允許你在最右邊的信標右邊再增加一個信標，功率隨意，問從右邊開始逐個啟動所有未被摧毀的信標，最後最少會有幾個信標被摧毀？
思路:
創一個陣列des紀錄所有信標在[0].右邊信標全數被摧毀(除了額外增加的信標)且當前信標被摧毀的狀況下被毀的最少總信標數，和[1]右邊信標全數被摧毀(除了額外增加的信標)且當前信標被啟動的狀況下被毀的最少總信標數。des[i][0] = min(des[i-1][0],des[i][1])，因為當前信標已毀，所以不影響未摧毀的總數及左邊的狀態，直接對左邊的取最小值；des[i][1] = des[s][1] – 1，由於當前信標未毀，所以會啟動將左邊當前功率內的信標摧毀，然後啟動左邊的信標，因此用二分搜尋找未被摧毀的最右邊信標s，然後將其最少被摧毀的信標數減1(因為當前信標未毀)。
程式碼:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <iostream> | |
| #include <algorithm> | |
| #include <cmath> | |
| using namespace std; | |
| const int AMAX = 1e5 + 7; | |
| struct Beacon | |
| { | |
| int a; | |
| int b; | |
| }; | |
| bool comp(Beacon a, Beacon b) | |
| { | |
| return a.a < b.a; | |
| } | |
| int N, des[AMAX][2], ans, s; | |
| Beacon beacon[AMAX]; | |
| void bsearch(int n, int l, int r) | |
| { | |
| if(l >= r) | |
| { | |
| return; | |
| } | |
| int mid = (l + r) / 2; | |
| if(beacon[mid].a < n) | |
| { | |
| s = max(s, mid); | |
| bsearch(n, mid + 1, r); | |
| } | |
| else | |
| { | |
| bsearch(n, l, mid); | |
| } | |
| return; | |
| } | |
| int main() | |
| { | |
| cin >> N; | |
| for(int i = 0; i < N; ++i) | |
| { | |
| cin >> beacon[i].a >> beacon[i].b; | |
| } | |
| sort(beacon, beacon + N, comp); | |
| ans = N - 1; | |
| des[0][0] = N; | |
| des[0][1] = N - 1; | |
| for(int i = 1; i < N; ++i) | |
| { | |
| des[i][0] = min(des[i - 1][0], des[i - 1][1]); | |
| s = -1; | |
| bsearch(beacon[i].a - beacon[i].b, 0, i); | |
| if(s == -1) | |
| { | |
| des[i][1] = N - 1; | |
| } | |
| else | |
| { | |
| des[i][1] = des[s][1] - 1; | |
| } | |
| ans = min(ans, min(des[i][0], des[i][1])); | |
| } | |
| cout << ans << endl; | |
| return 0; | |
| } |