Sunscreen

Time Limit:?1000MS	?	Memory Limit:?65536K
Total Submissions:?12907	?	Accepted:?4534

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 2 3 10 2 5 1 5 6 2 4 1

Sample Output

2

Source

?

題解：現在有一群奶牛在沙灘上曬太陽，需要涂防曬霜。求所能被防曬的奶牛最多的只數。

輸入：1st? 兩個用空格分開的整數? C L,分別代表 奶牛的頭數（cows） 和 防曬霜的 瓶數( lotion )。

2nd 接下來 C行，輸入 單只奶牛所需最小的防曬霜的防嗮系數 minSPF ,最大的? maxSPF,每行數據用空格隔開。

3rd 再接下來 L行 ，輸入 防曬霜的防曬系數t1 和瓶數 t2? 每行數據用空格隔開。

? 注意：不同行的防曬霜，他們的防曬系數可能一樣，所以可以用類似于桶排序中的桶的使用方法 用一個數組來存儲防曬霜瓶數，數組下標就是防曬系數。

?

思路：讀入數據->以奶牛的最小防曬系數為關鍵字 由高到低 排列 奶牛數據所在的結構體數組->循環遍歷奶牛：一只奶牛 再遍歷最高防曬系數j=maxspf 到最低防曬系數j>=minspf? j-- 查詢 （類似于桶排序）防曬霜數組 lo[j],一旦有防曬霜在

這個區間，那么可被防曬的奶牛數量加一，對應的 lo[j]? 即防曬系數spf=j 的防曬霜數量減一。條件是這個防曬霜數量不能少于1.

（所以就是貪心）

1 #include <iostream> 2 #include <stdio.h> 3 #include <cstring> 4 5 #include <algorithm> 6 using namespace std; 7 //bool vis[2509]; 8 struct cow{ 9 int mina; 10 int maxa; 11 }co[2509]; 12 13 bool cmpcow(cow x, cow y) 14 { 15 return x.mina>y.mina; 16 } 17 int lo[1009]; 18 //bool lotions(lotion x,lotion y) 19 //{ 20 // return x.spf<y.spf; 21 //} 22 int main() 23 { int c,l; 24 while(scanf("%d%d",&c,&l)!=EOF) 25 { 26 27 int sum=0; 28 // memset(vis,false,sizeof(vis)); 29 30 for(int i=1;i<=c;i++){ 31 scanf("%d%d",&co[i].mina,&co[i].maxa); 32 } 33 for(int i=1;i<=l;i++){ 34 int t1,t2; 35 scanf("%d%d",&t1,&t2);//type 36 // scanf("");//quantity 37 // lo[t1].spf=t1; 38 lo[t1]+=t2; 39 } 40 41 sort(co+1,co+c+1,cmpcow); 42 // sort(lo,lo+l,lotions); 43 44 for(int i=1;i<=c;i++){ 45 for(int j=co[i].maxa;j>=co[i].mina;j--){ 46 if(lo[j]) 47 { 48 sum++,lo[j]--; 49 break; 50 } 51 } 52 } 53 54 printf("%d",sum); 55 } 56 return 0; 57 }

?

。。。

轉載于:https://www.cnblogs.com/greenaway07/p/10662213.html

總結

以上是生活随笔為你收集整理的POJ 3614 Sunscreen的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。