已知在一個平面上有一定數(shù)量的氣球，平面可以看作一個坐標系，在平面的x軸的不同位 置安排弓箭手向y軸方向射箭，弓箭可以向y軸走無窮遠;給定氣球的寬度 xstart ≤ x ≤ xend，問至少需要多少弓箭手，將全部氣球打爆?

例如: 四個氣球 : [[10,16], [2,8], [1,6], [7,12]]，至少需要2個弓箭手。
如下過程

在射擊的過程中想要安排最少的弓箭手保證能夠完成所有氣球的射擊任務，我們可以從中尋找到貪心規(guī)律

1. 對于一個氣球，至少需要一個弓箭手才能夠射穿
2. 當一個弓箭手射穿一個氣球的同時盡可能多得射穿其他的氣球，這就是我們想要達到的安排最少弓箭手的方式

可以使用如下迭代策略：
維護一個射擊區(qū)間，保證在遍歷氣球的過程中射擊區(qū)間的左端點是小于右端點；否則就需要增加一個弓箭手，同時再維護一個新的射擊區(qū)間。

算法實現(xiàn)如下:

/*
貪心規(guī)律：
維護一個射擊區(qū)間，且該射擊區(qū)間不斷縮小，直到容納最多的氣球
*/
int get_least_shooter(vector<pair<int,int>> &bollon) {if (bollon.size() < 2) {return bollon.size();}int shooter = 1;/*排序的目的是為了保證氣球的起始值從小到大，隨著遍歷的進行，氣球的起始值逐漸增大*/sort(bollon.begin(),bollon.end(),cmp);int begin = bollon[0].first;//射擊區(qū)間的左邊界int end = bollon[0].second;//射擊區(qū)間的右邊界for (int i = 0;i < bollon.size(); ++i) {if (end >= bollon[i].first) { //當左邊界大于右邊界時停止維護射擊區(qū)間begin = bollon[i].first;if (end > bollon[i].second) {//不斷縮小右邊界的范圍end = bollon[i].second;}} else{shooter++;begin = bollon[i].first;end = bollon[i].second;}}return shooter;
}

測試代碼如下:

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;bool cmp(pair<int,int> a,pair<int,int> b) {return a.first < b.first;
}int get_least_shooter(vector<pair<int,int>> &bollon) {if (bollon.size() < 2) {return bollon.size();}int shooter = 1;sort(bollon.begin(),bollon.end(),cmp);int begin = bollon[0].first;int end = bollon[0].second;for (int i = 0;i < bollon.size(); ++i) {if (end >= bollon[i].first) {begin = bollon[i].first;if (end > bollon[i].second) {end = bollon[i].second;}} else{shooter++;begin = bollon[i].first;end = bollon[i].second;}}return shooter;
}int main(){vector<pair<int,int>> bollon;pair<int,int> a;cout <<"constuct the bollon " << endl;for (int i = 0;i < 5; ++i) {cin >> a.first;cin >> a.second;bollon.push_back(a);}cout << "the least of the shootors is " << get_least_shooter(bollon);return 0;
}

輸出結(jié)果如下

constuct the bollon 
10 16
2 8
1 6
7 12
20 21
the least of the shootors is 3

總結(jié)

以上是生活随笔為你收集整理的贪心：Burst Balloons 最少次数完成射击气球的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。