題目描述

某國為了防御敵國的導(dǎo)彈襲擊，發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。但是這種導(dǎo)彈攔截系統(tǒng)有一個缺陷：雖然它的第一發(fā)炮彈能夠到達任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達捕捉到敵國的導(dǎo)彈來襲。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。

輸入導(dǎo)彈依次飛來的高度（雷達給出的高度數(shù)據(jù)是≤50000 \le 50000≤50000的正整數(shù)），計算這套系統(tǒng)最多能攔截多少導(dǎo)彈，如果要攔截所有導(dǎo)彈最少要配備多少套這種導(dǎo)彈攔截系統(tǒng)。

輸入格式
1行，若干個整數(shù)（個數(shù)≤100000 \le 100000≤100000）

輸出格式
2行，每行一個整數(shù)，第一個數(shù)字表示這套系統(tǒng)最多能攔截多少導(dǎo)彈，第二個數(shù)字表示如果要攔截所有導(dǎo)彈最少要配備多少套這種導(dǎo)彈攔截系統(tǒng)。

輸入輸出樣例
輸入 #1
389 207 155 300 299 170 158 65

輸出 #1
6
2

解析

第一問相當于最長不上升子序列
第二問是貪心的思想

代碼

#include<cstdio> #include<cmath> #include<cstring> #include<algorithm> using namespace std; int tot=1; int x[100005]; int main(){while(scanf("%d",&x[tot])!=EOF){mx=max(mx,x[tot]);tot++;}tot--;int q[100005]={ },num1=0;for(int i=1;i<=tot;i++){if(q[num1]>=x[i]||num1==0){q[++num1]=x[i];continue;}int ans;for(ans=1;ans<=num1;ans++){if(q[ans]<x[i]) break;/*這里沒有等號，使結(jié)尾的min盡可能的大后面的元素才能盡可能的可以放到隊尾從而使隊列最長*/ }q[ans]=x[i];}int num=0;for(int i=1;i<=tot;i++){if(q[num]<x[i]){q[++num]=x[i];continue;}int st=1,ed=num,mid,ans=ed;for(ans=1;ans<=num;ans++){if(q[ans]>=x[i]) break;/*這里與上一問相比多個等號，使結(jié)尾的max盡可能的大后面才能盡可能的不需要增加一組*/ }q[ans]=x[i];}printf("%d\n%d",num1,num); }

總結(jié)

以上是生活随笔為你收集整理的不止代码：导弹拦截的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。