poj3614 Sunscreen【贪心】-白红宇

poj3614 Sunscreen【贪心】

阅读量：5329 次

发布时间：2019-06-14

本文共 2536 字，大约阅读时间需要 8 分钟。

Sunscreen

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 11772		Accepted: 4143

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 maximum SPF rating (1 ≤ minSPF_i ≤ 1,000; minSPF_i ≤ maxSPF_i ≤ 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 SPF_i (1 ≤ SPF_i ≤ 1,000). Lotion bottle i can cover cover_i 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

* Lines 2..C+1: Line i describes cow i's lotion requires with two integers: minSPF_i and maxSPF_i

* Lines C+2..C+L+1: Line i+C+1 describes a sunscreen lotion bottle i with space-separated integers: SPF_i and cover_i

Output

A single line with an integer that is the maximum number of cows that can be protected while tanning

Sample Input

3 23 102 51 56 24 1

Sample Output

Source

题意：

有c头牛，每头牛有一个区间。有l种防晒霜，每种有一个spf值和对应的瓶数。牛只能用在他区间内的防晒霜。问最多能有多少牛被涂。

思路：

按minspf排序，每次取minspf最高的一头牛，给他安排可以被安排的spf值最高的防晒霜。

因为我们这样排了序之后，能给minspf高的牛用的防晒霜肯定也能给minspf低一些的牛用。

这时候就要尽量用spf值高的。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             10 //#include 
              
               11 using namespace std;12 typedef long long LL;13 #define inf 0x7f7f7f7f14 15 int c, l;16 const int maxn = 2505;17 struct lotion{18 int spf;19 int cover;20 }lo[maxn];21 struct mow{22 int minspf, maxspf;23 }cow[maxn];24 25 bool cmpcow(mow a, mow b)26 {27 if(a.minspf == b.minspf){28 return a.maxspf < b.maxspf;29 }30 return a.minspf < b.minspf;31 }32 33 bool cmplo(lotion a, lotion b)34 {35 return a.spf < b.spf;36 }37 38 int main()39 {40 while(scanf("%d%d", &c, &l) != EOF){41 for(int i = 0; i < c; i++){42 scanf("%d%d", &cow[i].minspf, &cow[i].maxspf);43 }44 //cout<
               
                <<" "<
                
                 <
                 
                  = 0; i--){54 for(int j = l - 1; j >= 0; j--){55 if(lo[j].spf < cow[i].minspf)break;56 if(lo[j].spf <= cow[i].maxspf && lo[j].cover > 0 && lo[j].spf >= cow[i].minspf){57 lo[j].cover--;58 cnt++;59 break;60 }61 }62 }63 printf("%d\n", cnt);64 }65 return 0;66 }

转载于:https://www.cnblogs.com/wyboooo/p/9901449.html

你可能感兴趣的文章