C++题目描述游乐园举办了一场射气球的比赛如果谁能使用最少的弓箭数量引爆所有气球则会得到最佳射手奖。规则如下：在二维空间中有n个直径不同的球形气球对于每个气球提供的是水平方向上气球直径的开始和结束坐标。由于气球是被水平牵引的所以Y坐标并不重要因此只要知道气球直径的开始和结束的X坐标就足够了。每个气球的直径的开始坐标一定小于结束坐标。一支弓箭可以沿着X轴从不同点完全垂直地射出。在坐标X处射出一支箭若

思路：

首先，我们需要按照气球的结束坐标进行排序，这样可以保证尽可能多地引爆气球。

然后，我们从第一个气球开始遍历，每次记录当前引爆的气球的结束坐标。

如果下一个气球的开始坐标大于当前引爆的气球的结束坐标，说明需要再次射箭引爆新的气球，此时箭的数量加1，并更新当前引爆的气球的结束坐标为当前气球的结束坐标。

最后，返回箭的数量即可。

代码实现如下：

#include #include #include using namespace std;

bool compare(pair<int, int> a, pair<int, int> b){ return a.second < b.second; }

int main(){ int n; cin >> n;

vector<pair<int, int>> balloons;
for(int i=0; i<n; i++){
    int start, end;
    cin >> start >> end;
    balloons.push_back(make_pair(start, end));
}

sort(balloons.begin(), balloons.end(), compare);

int arrows = 1;
int end = balloons[0].second;

for(int i=1; i<n; i++){
    if(balloons[i].first > end){
        arrows++;
        end = balloons[i].second;
    }
}

cout << arrows << endl;

return 0;