题目大意：一堆牛，为了避免晒太阳会灼烧自己，然后他们自己有自己的防晒指数（一个区间），防晒霜可以提高防晒因数SPF，大了不行小了不行，现在有一桶防晒霜，他们提供一定的SPF，但是最多可以提供k头牛使用，问你这堆防晒霜最多可以给多少头牛提供保护？
大水题，我们用贪心就可以了，把防晒因数尽量给SPF_MIN大的用（还要比较SPF_MAX满足要求与否），就是建堆，然后不断贪心就可以了。
1 #include2 #include 3 #include 4 #include 5 6 using namespace std; 7 8 typedef struct cow_set_ 9 {10 int min_SPF;11 int max_SPF;12 }COWS;13 typedef struct lotion_set_14 {15 int SPF;16 int cover;17 bool operator < (const lotion_set_ &x) const //自定义比较函数18 {19 return SPF < x.SPF;//最大值优先20 }21 }Lotion;22 23 int fcomp(const void *a, const void *b)24 {25 if ((*(COWS *)a).min_SPF == (*(COWS *)b).min_SPF)26 {27 return (*(COWS *)b).max_SPF - (*(COWS *)a).max_SPF;28 }29 else30 return (*(COWS *)b).min_SPF - (*(COWS *)a).min_SPF;//由大到小排列31 }32 33 static COWS cows_set[2500];34 static bool used[2500];35 priority_queue que_lotion;36 37 void Search(const int);38 39 int main(void)40 {41 int cow_sum, lotion_sum;42 Lotion tmp;43 44 while (~scanf("%d%d", &cow_sum, &lotion_sum))45 {46 for (int i = 0; i < cow_sum; i++)47 scanf("%d%d", &cows_set[i].min_SPF, &cows_set[i].max_SPF);48 for (int i = 0; i < lotion_sum; i++)49 {50 scanf("%d%d", &tmp.SPF, &tmp.cover);51 que_lotion.push(tmp);52 } 53 qsort(cows_set, cow_sum, sizeof(COWS), fcomp);54 Search(cow_sum);55 }56 return 0;57 }58 59 void Search(const int cow_sum)60 {61 int ans = 0, tmp_cover;62 Lotion out;63 memset(used, 0, sizeof(used));64 65 while (!que_lotion.empty())66 {67 out = que_lotion.top(); que_lotion.pop();68 tmp_cover = out.cover;69 for (int j = 0; j < cow_sum && tmp_cover != 0; j++)70 {71 if (used[j]) continue;72 if (cows_set[j].max_SPF < out.SPF73 || cows_set[j].min_SPF > out.SPF)74 continue;75 76 used[j] = 1; ans++; tmp_cover--;77 }78 }79 printf("%d\n", ans);80 }
还有这一次用了STL的堆，不知道为什么STL的堆总是比我自己手动写的要慢一点，可能是因为STL要先要一片区域的原因