Problem Description 某國為了防御敵國的導彈襲擊,發展出一種導彈攔截系統.但是這種導彈攔截系統有一個缺陷:雖然它的第一發炮彈能夠到達任意的高度,但是以後每一發炮彈都不能超過前一發的高度.某天,雷達捕捉到敵國的導彈來襲.由於該系統還在試用階段,所以只有一套系統,因此有可能不能攔截所有的導彈.
8 389 207 155 300 299 170 158 65Sample Output
2
這道題是一個貪心題。
具體貪心過程就是:
每次讀入一個導彈高度,先判斷是否有炮可以攔截,如果沒有就要再加一個攔截系統,如果可以攔截,就要選擇一個攔截系統當前高度和目標導彈高度相差值最小的。這樣才能使高度損失達到最低.換句話說,現在有3個攔截系統,目前的最高高度分別是100,90, 80,現在要攔截一個85的炮彈那麼只能在100和90選一個,因為90和85相差比較近,高度損失小,所以選擇90的這個攔截系統進行攔截.
具體代碼實現思路:
用一個數組 f [ ] 表示當前的攔截系統個數已經分別的目前攔截高度.最開始只有一個,攔截高度自然是第一枚導彈的打擊高度,然後每次讀入一個導彈的打擊高度 H .然後在 f [ ] 數組中從左 f [ 0 ]開始找一個位置 i 使得 f [ i ] > H > f [ i-1 ] 當然如果f [ 0 ]比H大,那麼 i 自然就是0,找到了說明當前i的攔截系統就是能夠使高度損失最低的攔截系統,然後將該攔截系統的高度改為H,表示當前攔截系統已經把H的這個導彈攔截,如果沒找到滿足上式的這個位置i說嘛當前H已經超過了所有攔截系統的攔截高度,那麼我們就要再加入一個攔截系統,並把這個攔截系統的攔截高度改為H加入到f [ ] 最後表示已經攔截了H這個導彈。
最重要的:
在查找i位置的時候使用:
二分查找!!
#include#include using namespace std; #include int main() { int f[100000]; int i,a,n,t=0; int l,r,mid; while(scanf("%d",&n)!=EOF) { t=1; while(n--) { scanf("%d",&a); l=0,r=t; while(l<=r) //二分查找 { mid=(l+r)/2; if(f[mid]==a) { l=mid; break; } else if(f[mid]<=a) l=mid+1; else r=mid-1; } if(l