POJ 3614 Sunscreen（貪心）

POJ 3614 Sunscreen

題目鏈接

題意：轉自http://blog.csdn.net/sdj222555/article/details/10698641
有C個奶牛去曬太陽 (1 <=C <= 2500)，每個奶牛各自能夠忍受的陽光強度有一個最小值和一個最大值，太大就曬傷了，太小奶牛沒感覺。
而剛開始的陽光的強度非常大，奶牛都承受不住，然後奶牛就得塗抹防曬霜，防曬霜的作用是讓陽光照在身上的陽光強度固定為某個值。
那麼為了不讓奶牛燙傷，又不會沒有效果。
給出了L種防曬霜。每種的數量和固定的陽光強度也給出來了
每個奶牛只能抹一瓶防曬霜，最後問能夠享受曬太陽的奶牛有幾個。

思路： 貪心加優先隊列，牛按小值排序，防曬霜按spf值排序，然後每次一個防曬霜，就把可以的牛加入優先隊列，然後每次取出牛的時候，取出右值盡量小的即可

代碼：

#include 
#include 
#include 
#include 
using namespace std;

const int N = 2505;

int c, l;

struct SPF {
	int l, r;
	void read() {
		scanf("%d%d", &l, &r);
	}
	bool operator < (const SPF &c) const {
		return r > c.r;
	}
} spf[N], spf2[N];

bool cmp(SPF a, SPF b) {
	return a.l < b.l;
}

int main() {
	while (~scanf("%d%d", &c, &l)) {
		for (int i = 0; i < c; i++)
			spf[i].read();
		sort(spf, spf + c, cmp);
		for (int i = 0; i < l; i++)
			spf2[i].read();
		sort(spf2, spf2 + l, cmp);
		int u = 0;
		priority_queue Q;
		int ans = 0;
		for (int i = 0; i < l; i++) {
			while (u < c && spf[u].l <= spf2[i].l)
				Q.push(spf[u++]);
			while (!Q.empty() && spf2[i].r) {
				int tmp = Q.top().r;
				Q.pop();
				if (tmp < spf2[i].l) continue;
				spf2[i].r--;
				ans++;
			}
		}
		printf("%d\n", ans);
	}
	return 0;	
}