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。

第一眼看到这题目就是水题，直接模拟暴搜。做完后仔细一想1000000的数据会超时，

于是我重新作了一遍，用一个桶数组装气球的度，从后往前枚举，O(n)算法。

代码如下 ：

#include<iostream>
#include<cstdio>
using namespace std;
int n,i,j,k=1;
int a[1000001],t[1000001],dp[1000001];
int main()
{
	cin>>n;
	for(i=1;i<=n;i++) scanf("%d",&a[i]);
	for(i=n;i>=1;i--)
	{
		t[a[i]]++;
		if(t[a[i]-1]){dp[i]=dp[i+1];t[a[i]-1]--;}//前面有气球的话后面直接爆掉
		else dp[i]=dp[i+1]+1;没有的话说明要多一发子弹
	}
	cout<<dp[1];
	return 0;
}

最后

以上就是标致过客为你收集整理的气球 【解题报告】                                                                  2、气球    b.pas/cpp/c的全部内容，希望文章能够帮你解决气球 【解题报告】                                                                  2、气球    b.pas/cpp/c所遇到的程序开发问题。

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