气球（自我感觉良好）

                                 2、气球    b.pas/cpp/c

【题目描述】

      SM中学一年一度的体艺节马上开幕了，在一条笔直的塑胶跑道上，从左往右挂着N只气球，第i只气球的高度是Hi。奶牛Bessie喜欢搞恶作剧，于是它决定用气枪把所有的气球都打破。Bessie每次都是从塑胶跑道的最左边射出一颗子弹，Bessie可以在任意的高度开枪，然后子弹会水平的从最左边飞到最右边，当子弹一旦碰到某个气球时，该气球瞬间破裂，然后子弹的高度会降低1，子弹继续沿水平方向往右边飞过去，如果再碰到气球，气球也会瞬间破裂，子弹的高度再次降低1，然后继续水平的往右边飞去……。那么Bessie至少要发射多少颗子弹，才能把所有的气球打破？

【输入格式】b.in

     第一行，一个整数N。 1 <= N <= 1000000。

第二行，N个整数，第i个整数是Hi。  1<=Hi <= 1000000。
【输出格式】b.out

      一个整数，最少的子弹数量。

【数据规模】

       对于40%的数据，  N <= 4000。

//用桶的思想（注意，拦截导弹会超时）
#include <cstdio>
#include <cstdlib>
using namespace std;


const int maxn=1000000+15;
int n;
int hh[maxn];
int tj[maxn];
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&hh[i]);
	int ans=0;
	for (int i=1;i<=n;i++)
	{
		if (tj[hh[i]]==0)
		{
			ans++;
			tj[hh[i]-1]++;
			continue;
		}
		tj[hh[i]]--;
		tj[hh[i]-1]++;
	}
	printf("%dn",ans);
	return 0;
}

最后

以上就是着急橘子为你收集整理的气球（自我感觉良好）的全部内容，希望文章能够帮你解决气球（自我感觉良好）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。