贪心算法是指在对问题求解时,做出在当前看来是最优解,从局部最优到全局最优。
射气球 1
问题描述:某房间内漂浮着n个气球,它们从左到右排成一列。每次你可以在最左边从任意高度向右射箭,箭会笔直前进。在高度 h 上飞行的箭,击破气球瞬间,高度变为h-1。最少需要射多少支箭才能击破所有气球。假设气球可以看作一个点,箭的下降时间忽略不计。
输入:5 输出:2
2 1 5 4 3
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
int a[n],b;
for (int i=1;i<=n;i++)
{
int h;
cin>>h;
if (!a[h]){
b++;
a[h-1]++;
}else{
a[h]--;
a[h-1]++;
}
}
}