题目描述 小明喜欢武侠小说，在武侠世界里，他不但练就了一箭双雕的能力，还可以一箭多雕。 现在所有雕在一条直线上从左到右排列，但是他们的高度不同。而小明想要把他们都射下来。小明使用的是一种特殊的弓箭，他可以将弓箭射到任意一个高度为H的雕，当射中一个高度为H的雕后，弓箭的高度会下降到H-1，再从左到右飞行，直到射到高度为H-1的大雕，再降低1的高度，直到飞出大雕的队列。 由于弓箭数量有限，小明想要知道，最少用多少的弓箭，就可以射下所有的大雕。 输入 第一行一个整数，n表示直线上的大雕数量。 第二行n个整数，表示从左到右每个大雕的高度。 输出 输出一个整数，表示最少用的弓箭数量。 样例输入 5 2 1 5 4 3
5 1 2 3 4 5
5 4 5 2 1 4 样例输出 2
5
3 提示 【样例解释1】 第一箭射向第一个大雕，射中后高度下降到1,会射中第二只大雕。 第二箭射向第三个大雕，依次射中高度为5,4,3的三只大雕。 60分的数据n不超过1000000,高度不超过1000000 100分数据，n小于1000000。高度不超过1000000000 30分数据 n小于5000，高度不超过1000000 60分数据n小于1000000
暴力的思维很好想，n^2直接搞。 其实满分也不难，可以这么想： 保存下当前所有的箭，然后对于当前i，去匹配一个高度为hi+1的箭，找不到就另开一个箭。 那么怎么快速找到箭并修改呢？ 链表
#include<cstdio>#include<iostream>#include<algorithm>using namespace std;int n,x,h,now,ans;int a[1000005],p[1000005],c[1000005];int head[1000005],Next[1000005];struct ty{ int v,id;}b[1000005];bool cmp(ty x,ty y){ return x.v<y.v;}int main(){ cin>>n; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); b[i].v=a[i]; b[i].id=i; } sort(b+1,b+n+1,cmp); b[0].v=-1e9; for(int i=1;i<=n;i++) { if(b[i].v!=b[i-1].v) x++; p[x]=b[i].v; //离散化后的x对应的真实值 c[b[i].id]=x; } for(int i=1;i<=x;i++) head[i]=-1; for(int i=1;i<=n;i++) { h=c[i]; if(h+1<=x&&p[h+1]==a[i]+1&&head[h+1]!=-1) { now=head[h+1]; head[h+1]=Next[head[h+1]]; Next[now]=head[h]; head[h]=now; } else { ans++; Next[ans]=head[h]; head[h]=ans; } } cout<<ans; return 0;}新闻热点
疑难解答
