天天看點

poj3614 Sunscreen 【優先隊列】

題意

有C個奶牛去曬太陽 (1 <=C <= 2500),每個奶牛各自能夠忍受的陽光強度有一個最小值和一個最大值,太大就曬傷了,太小奶牛沒感覺。

而剛開始的陽光的強度非常大,奶牛都承受不住,然後奶牛就得塗抹防曬霜,防曬霜的作用是讓陽光照在身上的陽光強度固定為某個值。

那麼為了不讓奶牛燙傷,又不會沒有效果。

給出了L種防曬霜。每種的數量和固定的陽光強度也給出來了

每個奶牛隻能抹一瓶防曬霜,最後問能夠享受曬太陽的奶牛有幾個。

那麼将奶牛按照陽光強度的最小值從小到大排序。

将防曬霜也按照能固定的陽光強度從小到大排序

從最小的防曬霜枚舉,将所有符合  最小值小于等于該防曬霜的 奶牛的 最大值 放入優先隊列之中。

然後優先隊列是小值先出

是以就可以将這些最大值中的最小的取出來。更新答案。

注意priority_queue的聲明priority_queue<int, vector<int>, greater<int> > que;