Massive Algorithms: POJ 3614 [zoj 3508] -- Sunscreen

POJ 3614 [zoj 3508] -- 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 ≤ minSPF_i ≤ 1,000; minSPF_i ≤ maxSPF_i ≤ 1,000) that will work. If theSPF 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

Sample Output

https://blog.csdn.net/qq1169091731/article/details/51932467

设C个奶牛的防晒区间分别为（L1，R1） ( L2 , R2 ) ( L3 ,R3) ……( Ln ,Rn) ,L 种防晒霜(SPF1, num1) (SPF2,num2) …… (SPFn, num n)

①要想使尽可能多的奶牛能够享受阳光，主要取决于防晒霜，应尽量使防晒霜SPF小的应用于防晒区间小的，并且在SPF，num值允许的情况下尽量涉及到每个区间，才是最佳的

②将C个奶牛的防晒区间按照左端点从小到大的顺序排序，左端点相同的按照右端点从小到大排序，将L种防晒霜按照防晒系数SPF从小到大排序

③从小到大遍历每种防晒霜，针对防晒霜Li ,首先确定能够被其作用的奶牛区间，即满足条件 L <= Li. SPF<=R d的奶牛区间，在这些区间当中优先选择R最小的那个区间，因为大区间（R比较大）的奶牛有更大的选择空间，而R小的能选择的空间比较小，让其优先使用防晒霜。这样就能保证整个过程尽可能多的奶牛使用合适的防晒霜。

https://blog.csdn.net/Akatsuki__Itachi/article/details/75634181

题意：有C头奶牛，她们去海边玩耍吧！但是阳光强度特别高，她们能忍受的辐射强度有个范围，即min～max，高于max奶牛就被晒伤了，低于max奶牛没什么感觉。现在有L瓶防晒霜，前面的数据代表这种防晒霜能把SPF值固定在某个值上，使奶牛不被晒伤，后面数据代表这种防晒霜就几瓶。

解题思路：将奶牛能承受的最小值min从小到大排序，防晒霜的SPF值也从小到大排序。对于每一瓶防晒霜将所有合适的奶牛遍历一遍，即如果防晒霜的SPF值大于奶牛所能承受的min值，就将她的最大值入到优先队列(从小到大排序的)，然后再次判断这个spf值是否小于队列的队首，如果符合就出队，同时数量-1.

https://blog.csdn.net/sdj222555/article/details/10698641

从最小的防晒霜枚举，将所有符合最小值小于等于该防晒霜的奶牛的最大值放入优先队列之中。

然后优先队列是小值先出

所以就可以将这些最大值中的最小的取出来。更新答案。

http://www.voidcn.com/article/p-mqestlhe-ec.html
https://www.cnblogs.com/douzujun/p/6853516.html

https://www.cnblogs.com/dilthey/p/6804156.html

把牛按minSPF从小到大排序一下，防晒霜按SPF排序一下。

然后遍历防晒霜lontion[1...L]，对于lotion[i]，把所有满足minSPF小于等于lontion[i].SPF的牛都找出来，入队。

我们将这个队列定义为按cow[i].maxSPF的从小到大排序的优先队列，那么，每次取出的队首，都是当前要求最苛刻（SPF要求范围最小的）那头牛，先满足这些牛，如果当前这种防晒霜能满足这头牛，就用掉一瓶，否则就放弃这头牛。

反复如此，直到所有防晒霜用完。

 5 struct Cows{
 6     int minSPF,maxSPF;
 7     bool operator<(const Cows &oth)const
 8     {
 9         return maxSPF>oth.maxSPF;
10     }
11 }cow[2505];
12 struct Lotions{
13     int SPF,cover;
14 }lotion[2505];
15 bool cmp1(Lotions a,Lotions b) {return a.SPF<b.SPF;}
16 bool cmp2(Cows a,Cows b) {return a.minSPF<b.minSPF;}
17 int main()
18 {
19     int C,L;
20     priority_queue<Cows> q;
21     scanf("%d%d",&C,&L);
22     for(int i=1;i<=C;i++) scanf("%d%d",&cow[i].minSPF,&cow[i].maxSPF);
23     for(int i=1;i<=L;i++) scanf("%d%d",&lotion[i].SPF,&lotion[i].cover);
24     sort(lotion+1,lotion+L+1,cmp1);
25     sort(cow+1,cow+C+1,cmp2);
26     int now=1,ans=0;
27     for(int i=1;i<=L;i++)
28     {
29         while(now <= C && cow[now].minSPF <= lotion[i].SPF)//由于事先排过序，所以当前这头一旦不满足cow[now].minSPF <= lotion[i].SPF，之后的牛都不满足 
30         {
31             q.push(cow[now]);
32             now++;
33         }
34         while(!q.empty() && lotion[i].cover>0)//要么是当前这种防晒霜很多，把所有牛都涂了；要么就是当前这种防晒霜用完了
35         {
36             if(q.top().maxSPF >= lotion[i].SPF)//这种防晒霜可以给这头牛涂
37             {
38                 ans++;//能涂的牛的数量增加1 
39                 lotion[i].cover--;//当前这种防晒霜用去一瓶
40             }
41             q.pop();//涂的上就涂，涂不上就放弃
42         }
43     }
44     printf("%d\n",ans);
45 }

http://www.hankcs.com/program/cpp/poj-3614-sunscreen.html奶牛美容：有C头奶牛日光浴，每头奶牛分别需要minSPF_i和maxSPF_i单位强度之间的阳光。现有L种防晒霜，分别能使阳光强度稳定为SPF_i，其瓶数为cover_i。求最多满足多少头奶牛

最小堆

2.4 加工并储存数据的数据结构

优先队列

首先得确定一个贪心策略，在满足minSPF的条件下，尽量把SPF小的防晒霜用在maxSPF小的奶牛身上，因为maxSPF大的奶牛有更大的选择空间。用一个最小堆q维护maxSPF的最小值，可以高效解决问题。

pair<int, int> cow[2500 + 16];

pair<int, int> bottle[2500 + 16];

priority_queue<int, vector<int>, greater<int> > q;    // 优先级队列，小元素优先出队

///////////////////////////SubMain//////////////////////////////////

int main(int argc, char *argv[])

{

#ifndef ONLINE_JUDGE

    freopen("in.txt", "r", stdin);

    freopen("out.txt", "w", stdout);

#endif

    int C, L;

    cin >> C >> L;

    for (int i = 0; i < C; ++i)

{

        cin >> cow[i].first >> cow[i].second;

}

    for (int i = 0; i < L; ++i)

{

        cin >> bottle[i].first >> bottle[i].second;

}

    sort(cow, cow + C);

    sort(bottle, bottle + L);

    int cur = 0; // 现在正等待涂防晒霜的奶牛的index

    int result = 0;

    for (int i = 0; i < L; ++i)

{

        while (cur < C && cow[cur].first <= bottle[i].first)

{

            q.push(cow[cur].second);

            ++cur;

}

        while (!q.empty() && bottle[i].second)

{

            int maxSPF = q.top(); q.pop();

            // “奶牛上限”比这一瓶的上限大，说明这头奶牛可以被涂上防晒霜

            if (maxSPF >= bottle[i].first)

{

                ++result;

                --bottle[i].second;

}

            // else 这头奶牛不能被涂上，因为bottle是按SPF排过序的，没有比这瓶更小的SPF了

}

}

    cout << result << endl;

#ifndef ONLINE_JUDGE

    fclose(stdin);

    fclose(stdout);

    system("out.txt");

#endif

    return 0;

}

http://blog.csdn.net/qq7366020/article/details/18186277

#define MAX 2600
struct snode{
int x,y;
}Num1[MAX],Num2[MAX];
bool cmp(struct snode a,struct snode b)
{
return a.y<b.y?true:false;
}
bool comp(struct snode a,struct snode b)
{
return a.x<b.x?true:false;
}
int main()
{
int i,j,n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=1;i<=n;i++)
{
scanf("%d%d",&Num1[i].x,&Num1[i].y);
}
for(i=1;i<=m;i++)
{
scanf("%d%d",&Num2[i].x,&Num2[i].y);
}
sort(Num1+1,Num1+1+n,cmp); //Cow按MaxSPF从小到大排
sort(Num2+1,Num2+1+m,comp); //bottle按从小到大排
int sum=0;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if(Num2[j].y>=1&&Num2[j].x>=Num1[i].x&&Num2[j].x<=Num1[i].y) //找到第一个符合条件
{
sum++;
Num2[j].y--;
break;
}
else if(Num2[j].x>Num1[i].y) //若bottle的SPF比cow的MaxSPF还大则退出循环
break; //剪枝
}
}
printf("%d\n",sum);
}
return 0;
}

http://www.acmsearch.com/article/show/20416
数据弱用网络流水过，Dinic只用了125ms，二分图多重匹配也行。

POJ 3614 [zoj 3508] -- Sunscreen

Labels

Popular Posts