題目描述 小明喜歡武俠小說，在武俠世界里，他不但練就了一箭雙雕的能力，還可以一箭多雕。 現(xiàn)在所有雕在一條直線上從左到右排列，但是他們的高度不同。而小明想要把他們都射下來。小明使用的是一種特殊的弓箭，他可以將弓箭射到任意一個高度為H的雕，當(dāng)射中一個高度為H的雕后，弓箭的高度會下降到H-1，再從左到右飛行，直到射到高度為H-1的大雕，再降低1的高度，直到飛出大雕的隊列。 由于弓箭數(shù)量有限，小明想要知道，最少用多少的弓箭，就可以射下所有的大雕。 輸入 第一行一個整數(shù)，n表示直線上的大雕數(shù)量。 第二行n個整數(shù)，表示從左到右每個大雕的高度。 輸出 輸出一個整數(shù)，表示最少用的弓箭數(shù)量。 樣例輸入 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分的數(shù)據(jù)n不超過1000000,高度不超過1000000 100分數(shù)據(jù)，n小于1000000。高度不超過1000000000 30分數(shù)據(jù) n小于5000，高度不超過1000000 60分數(shù)據(jù)n小于1000000
暴力的思維很好想，n^2直接搞。 其實滿分也不難，可以這么想： 保存下當(dāng)前所有的箭，然后對于當(dāng)前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對應(yīng)的真實值 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;}新聞熱點
疑難解答
