C語言貪心-最少攔截系統(Hdu 1257)

C語言貪心-最少攔截系統(Hdu 1257)

 

Problem Description 某國為了防御敵國的導彈襲擊,發展出一種導彈攔截系統.但是這種導彈攔截系統有一個缺陷:雖然它的第一發炮彈能夠到達任意的高度,但是以後每一發炮彈都不能超過前一發的高度.某天,雷達捕捉到敵國的導彈來襲.由於該系統還在試用階段,所以只有一套系統,因此有可能不能攔截所有的導彈.
怎麼辦呢?多搞幾套系統呗!你說說倒蠻容易,成本呢?成本是個大問題啊.所以俺就到這裡來求救了,請幫助計算一下最少需要多少套攔截系統.
Input 輸入若干組數據.每組數據包括:導彈總個數(正整數),導彈依此飛來的高度(雷達給出的高度數據是不大於30000的正整數,用空格分隔)
Output 對應每組數據輸出攔截所有導彈最少要配備多少套這種導彈攔截系統.
Sample Input

8 389 207 155 300 299 170 158 65

Sample 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