C++ 中找到射破所有气球所需的最少箭数

2025 年 5 月 12 日 | 阅读 4 分钟

在本文中，我们将讨论如何在 C++ 中找到射爆所有气球所需的最小箭数。

问题陈述

给定一个大小为 N 的数组，其中 points[i] 表示一个气球覆盖 X 坐标在 points[i][0] 和 points[i][1] 之间的区域。Y 坐标无关紧要。每个气球都必须被射爆。一支箭可以从点 (x, 0) 射出，射爆满足条件 points[i][0] <= x <= points[i][1] 的任何气球。箭到达目标后垂直向上飞行。目标是找到射爆所有气球所需的最小箭数。

我们可以使用以下步骤来确定射爆每个气球所需的最小箭数：

以其终点位置作为起点，对气球进行排序。
设置一个变量来记录所需的箭数，另一个变量来记录气球当前的结束坐标。
逐一检查所有已排序的气球。如果当前气球的起始坐标大于之前存储的结束坐标，则将结束坐标更新为当前气球的结束坐标，并增加箭数。
如果当前气球的起始坐标位于存储的结束坐标范围内，则将存储的结束坐标更新为保存的结束坐标和当前气球的结束坐标之间的较小值。

示例

气球：{{10, 16}, {2, 8}, {1, 6}, {7, 12}}
按结束坐标排序：{{1, 6}, {2, 8}, {7, 12}, {10, 16}}
射爆所有气球所需的箭数：2
气球：{{1, 2}, {3, 4}, {5, 6}, {7, 8}}
按结束坐标排序：{{1, 2}, {3, 4}, {5, 6}, {7, 8}}
射爆所有气球所需的箭数：4
气球：{{1, 2}, {2, 3}, {3, 4}, {4, 5}}
按结束坐标排序：{{1, 2}, {2, 3}, {3, 4}, {4, 5}}
射爆所有气球所需的箭数: 2

伪代码

 
function findMinArrowShots(balloons):
    if balloons are empty:
     return 0
    Sort balloons by end coordinate
    arrows = 1
    end = balloons[0].end
    for i from 1 to length of balloons:
        if balloons[i].start > end:
            arrows++
end=balloons[i].end
        else:
            end = min(end, balloons[i].end)
    return arrows   

示例 1

查看一个示例程序，以查找射爆 cpp 中所有气球所需的最小箭数

 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int findMinArrowShots(vector<vector<int>>& point) {
    if (point.empty()) return 0;
    sort(point.begin(), point.end(), [](const vector<int>& x, const vector<int>& y) {
        return x[1] < y[1];
    });
    int arrows = 1;
    int end = point[0][1];
    for (int i = 1; i < point.size(); i++) {
        if (point[i][0] > end) {
            arrows++;
            end = point[i][1];
        } else {
            end = min(end, point[i][1]);
        }
    }
    return arrows;
}
int main() {
    vector<vector<int>> balloons = {{10, 16}, {2, 8}, {1, 6}, {7, 12}};
    cout << "Minimum number of arrows needed: " << findMinArrowShots(balloons) << endl;
    return 0;
}   

输出

Find Minimum Number of Arrows Needed To Burst All Balloons in C++

示例 2

让我们再举一个例子，找出在 C++ 中射爆所有气球所需的最小箭数。

 
#include <bits/stdc++.h>
using namespace std;
bool cmp(vector<int> a, vector<int> b)
{
	return b[1] > a[1];
}
int minArrows(vector<vector<int>> points)
{
	// To sort our array according
	// to end position of balloons
	sort(points.begin(), points.end(), cmp);
	// Initialize end variable with
	//The end of the first balloon
	int end = points[0][1];
	// Initialize arrow with 1
	int arrow = 1;
	// Iterate through the entire
	// arrow of points
for (int i=1;i<points.size();++i)
	{
		// If the start of ith balloon
		// <= end than do nothing
		if (points[i][0] <= end)
		{
			continue;
		}
		else
		{
			// Update the new end
			end=points[i][1];
			arrow++;
		}
	}
	return arrow;
}
// Driver code
int main()
{

	vector<vector<int>> points = {{10, 16}, {2, 8}, {1, 6}, {7, 12}};
	cout << (minArrows(points));
	return 0;
}   

输出

示例 3

让我们再看一个例子，找出在 C++ 中射爆所有气球所需的最小箭数。

 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Balloon {
    int start;
    int end;
    Balloon(int s, int e) : start(s), end(e) {}
};
int findMinArrowShots(vector<Balloon>& balloons) {
    if (balloons.empty()) return 0;
    sort(balloons.begin(), balloons.end(), [](const Balloon& x, const Balloon& y) {
        return x.end < y.end;
    });
    int arrs = 1;
    int end = balloons[0].end;
    for (int i = 1; i < balloons.size(); i++) {
        if (balloons[i].start > end) {
            arrs++;
            end = balloons[i].end;
        } else {
            end = min(end, balloons[i].end);
        }
    }
    return arrs;
}
int main() {
    vector<Balloon> balloons = {Balloon(10, 16), Balloon(2, 8), Balloon(1, 6), Balloon(7, 12)};
    cout << "Minimum number of arrows needed: " << findMinArrowShots(balloons) << endl;
    return 0;
}   

输出

下一个主题C++ 中的香农-范诺解码

C++ 中找到射破所有气球所需的最少箭数

问题陈述

示例

伪代码

示例 1

示例 2

示例 3

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 中找到射破所有气球所需的最少箭数

问题陈述

示例

伪代码

示例 1

示例 2

示例 3

相关帖子

基于数组的队列与基于链表的队列的区别

C++ 封装索引

C++ 中的中心七边形数

C++ 中带有海洋景观的建筑

C++ 中的线路拼接

C++ 中的 std::basic_istream::sentry

C++ STL 中的 UTF-8 到宽字符转换

C++ 中计算黄金分割率序列

C++ 中的超图实现

C++ 预处理器指令与函数模板的区别

订阅 Tpoint Tech

联系信息

关注我们

教程