poj 3614 Sunscreen(优先队列+贪心)
生活随笔
收集整理的這篇文章主要介紹了
poj 3614 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 maximum SPF 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 * Lines 2..C+1: Line i describes cow i's lotion requires with two integers: minSPFi and maxSPFi * Lines C+2..C+L+1: Line i+C+1 describes a sunscreen lotion bottle i with space-separated integers: SPFi and coveriOutput 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 USACO 2007 November Gold 題意：有C個奶牛去曬太陽 (1 <=C <= 2500)，每個奶牛各自能夠忍受的陽光強度有一個最小值和一個最大值，太大就曬傷了，太小奶牛沒感覺。 而剛開始的陽光的強度非常大，奶牛都承受不住，然后奶牛就得涂抹防曬霜，防曬霜的作用是讓陽光照在身上的陽光強度固定為某個值。 那么為了不讓奶牛燙傷，又不會沒有效果。 給出了L種防曬霜。每種的固定的陽光強度和數量也給出來了 每個奶牛只能抹一瓶防曬霜，最后問能夠享受曬太陽的奶牛有幾個。 ? 思路：剛開始想錯了，正確的方法為： ????????? 1、將牛按最小值從小到大排好序 ????????? 2、將防嗮霜按陽光強度從小到大排好序 ????????? 3、然后有一個優先隊列，優先隊列里按牛的最大值從小到大排序 ????????? 4、遍歷防曬霜，將牛的最小值<=防曬霜的值的牛push進優先隊列，然后根據防曬霜的數量從隊首開始選出符合的牛，這部分見代碼 ????????? 5、while(k<n && cow[k].l<=p[i].x)注意這里的判斷條件要寫在一起，剛開始分開寫，將第二個條件寫在下面的if中，結果TLE了。。。。。。 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<queue> 5 #include<algorithm> 6 #include<vector> 7 using namespace std; 8 #define N 2600 9 int n,m; 10 struct Node{ 11 int l,r; 12 bool friend operator < (Node a,Node b){ 13 return a.r>b.r; 14 } 15 }cow[N]; 16 struct Node1{ 17 int x,num; 18 }p[N]; 19 bool cmp(Node a,Node b){ 20 return a.l<b.l; 21 } 22 bool cmp1(Node1 a,Node1 b){ 23 return a.x<b.x; 24 } 25 int main() 26 { 27 while(scanf("%d%d",&n,&m)==2){ 28 29 for(int i=0;i<n;i++){ 30 scanf("%d%d",&cow[i].l,&cow[i].r); 31 } 32 for(int i=0;i<m;i++){ 33 scanf("%d%d",&p[i].x,&p[i].num); 34 } 35 sort(cow,cow+n,cmp); 36 sort(p,p+m,cmp1); 37 38 //for(int i=0;i<v.size();i++){ 39 // printf("---%d\n",v[i]); 40 //} 41 42 priority_queue<Node>q; 43 44 int k=0; 45 int ans=0; 46 for(int i=0;i<m;i++){ 47 while(k<n && cow[k].l<=p[i].x){ 48 q.push(cow[k]); 49 k++; 50 } 51 52 int w=0; 53 while(!q.empty()){ 54 55 if(w>=p[i].num) break; 56 57 Node tmp=q.top(); 58 if(tmp.r>=p[i].x){ 59 q.pop(); 60 ans++; 61 w++; 62 } 63 else{ 64 q.pop(); 65 } 66 67 } 68 } 69 printf("%d\n",ans); 70 } 71 return 0; 72 } View Code? |
轉載于:https://www.cnblogs.com/UniqueColor/p/4768231.html
總結
以上是生活随笔為你收集整理的poj 3614 Sunscreen(优先队列+贪心)的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 县武装部军车驾驶员是士兵吗
- 下一篇： 重新设计一款Android App，我会