|
Sunscreen
Description To avoid unsightly burns while tanning, each of the C (1 ≤ C ≤ 2500) cows must cover her hide with sunscreen when they're at the beach. Cow i has a minimum and maximumSPF rating (1 ≤ minSPFi ≤ 1,000; minSPFi ≤ maxSPFi ≤ 1,000) that will work. If the SPF rating is too low, the cow suffers sunburn; if the SPF rating is too high, the cow doesn't tan at all........ The cows have a picnic basket with L (1 ≤ L ≤ 2500) bottles of sunscreen lotion, each bottle i with an SPF rating SPFi (1 ≤ SPFi ≤ 1,000). Lotion bottle i can cover coveri cows with lotion. A cow may lotion from only one bottle. What is the maximum number of cows that can protect themselves while tanning given the available lotions? Input
* Line 1: Two space-separated integers: C and L Output A single line with an integer that is the maximum number of cows that can be protected while tanning Sample Input 3 2 3 10 2 5 1 5 6 2 4 1 Sample Output 2 Source |
题目大意：一群奶牛去晒日光浴。有L瓶防晒霜，每瓶防晒霜有一个SPF（防晒系数），最多可以给cover头牛使用。共有C头牛，每头牛有minSPF和maxSPF，表示其可以使用的防晒霜的SPF区间，求最多可以让几头牛涂好防晒霜。
话说为什么这几天做的题目有这么多贪心，还有这么多堆呢？
乍一眼看是网络流，再看数据范围要TLE，结果看了题解发现是贪心。话说以前我出过一道网络流的题，结果被同学们贪心秒出了……
把奶牛按minSPF从小到大排序，防晒霜按SPF从小到大排序。枚举防晒霜，在所有可以使用该防晒霜的牛中选择maxSPF最小的牛。选牛的操作可以用堆来维护。
代码在此。
评论 (0)
