青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

pku2902 Intercepting Missiles 線段樹+離散化+二分圖匹配，注意C++短路

題意：
有b個炸彈，p個飛機，平行于x軸飛行，地面部署了m個導彈，只能垂直打。知道0時刻炸彈、飛機的坐標，以及導彈的坐標以及炸彈、導彈、飛機的速度，問不打到飛機的情況下最多能攔截多少導彈？
給力條件：炸彈被導彈擊中后，繼續飛行，而導彈立刻消失。飛行物高度均不同
有個注意點：注意C++中的短路問題，慎用兩個函數相或、與，可能因此一個函數得不到執行，這個在線段樹里是很麻煩的。寧可多寫一步

解法：
上次比賽這題死都A不掉，今天重新做了下，1A。。
首先，看到這題肯定想到二分圖的匹配模型。這個不細說，說下之前的處理。
首先，按照飛行物高度排序，然后枚舉導彈i能否打到j個炸彈，計算該導彈打到每個飛行物的時間區間，看區間有沒有被完全覆蓋即可判斷。這里用到線段樹。然后就是可惡的精度問題，其實，這題完全能夠避免精度誤差，將所有坐標預先乘以三種速度的最小公倍數，然后離散化再用線段樹來統計就沒問題了。區間處理還要注意一點就是處理成左閉右開區間，用[s*2,e*2-1)即可。

代碼：

posted on 2011-01-31 18:35 yzhw 閱讀(263) 評論(0)  編輯 收藏 引用 所屬分類: graph 、data struct