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

輸入導彈依次飛來的高度（雷達給出的高度數據是不大于30000的正整數，導彈數不超過1000），計算這套系統最多能攔截多少導彈，如果要攔截所有導彈最少要配備多少套這種導彈攔截系統。

【輸入】

輸入導彈依次飛來的高度。

【輸出】

第一行：最多能攔截的導彈數；

第二行：要攔截所有導彈最少要配備的系統數。

【輸入樣例】

389 207 155 300 299 170 158 65

【輸出樣例】

6 2

對于第一問，我們采用的是一種較為巧妙地方法，題目讓求的是最多能攔截的導彈數，并沒有讓求具體的是哪些導彈，因此，我們在考慮問題是就不必深究具體的導彈，只要所有的情況都涉及到就可以了。

我們的具體思路是如果后面的數小于我們有的數就把數組擴大一個，把這個數放入序列中，形成遞減序列，如果這個數大于前面的數，那么我們就把這個數以代替的形式放入數組中，代替的是小于它的最大整數。

按照這種思路來分析上面的樣例?

第一個數為389，第二個數為207 ，小于389，加入序列，同理，155加上序列，當300加入時，我們要將序列中的207替換

?就序列是黑色那條，新序列是紅色那條，就這樣一直往后取入數據?

最終，我們可以得到這樣一個序列，?那么，為什么我們可以以這個為答案呢，其實，只要把我們每一步分析的過程都補齊，就會看到這樣的結果

?下面三個可以省略

?

可以看到，其實在我們替換的過程中，就已經把所有可能的長序列都已經考慮到了，因此我們這樣做所得到的答案是沒有問題的。

總結

以上是生活随笔為你收集整理的洛谷-导弹拦截的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。