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。
输入样例 b.in
输出样例 b.out
样例解释
5
2 1 5 4 3
2
设定第一颗子弹高度是2，从最左边往最右边发射过去，这样第一、第二个气球会被射破。
设定第二个子弹高度是5，从最左边往最右边射过去，第三、第四、第五个气球会被射破。
5
1 2 3 4 5
5
5
4 5 2 1 4
3
设定第一颗子弹高度是4，从最左边往最右边发射过去，这样第一个气球会被射破。
设定第二个子弹高度是5，从最左边往最右边射过去，第二、第五个气球会被射破。
设定第三个子弹高度是2，从最左边往最右边射过去，第三、第四个气球会被射破。
//用桶的思想（注意，拦截导弹会超时） #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("%d\n",ans); return 0; }
