POJ3614-Sunscreen

Sunscreen Time Limit: 1000MS Memory Limit: 65536KTotal Submissions: 9975 Accepted: 3478

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 题目：奶牛美容：有C头奶牛日光浴，每头奶牛分别需要mini和maxi单位强度之间的阳光。 现有L种防晒霜，分别能使阳光强度稳定为SPF_i，其瓶数为cover_i。求最多满足多少头奶牛？

个人理解:

一共C头牛 第i头牛 需要的阳光强度 ∈[mini,maxi] 有L种防晒霜 第i瓶能让阳光强度稳定在SPFi 且第i种有coveri瓶 问 最多能满足多少头牛 假设第i种防晒霜 对于这瓶防晒霜 可能会有多头牛 能适合即 SPFi ∈[mini,maxi] 那么这瓶最好给谁呢？ 当然是给maxi小的牛 因为 maxi大的牛可能别的防晒霜也适合 即它的选择的空间大 即: 在满足minSPF的条件下，尽量把SPF小的防晒霜用在maxSPF小的奶牛身上， 因为maxSPF大的奶牛有更大的选择空间。用一个最小堆来维护 将奶牛按照阳光强度的最小值从小到大排序。 将防晒霜也按照能固定的阳光强度从小到大排序 从最小的防晒霜枚举，将所有符合 最小值小于等于该防晒霜的 奶牛的 最大值 放入最小堆之中。 然后堆中最小值先出 就可以将这些最大值中的最小的取出来。更新答案。

运行结果1:

ResultMemoryTimeLanguageCode lengthAccepted176KB0MSC1608B

代码用的快速排序和最小堆   第二名 毕竟是自己写的数据结构 这样也挺好^!^

# include <stdio.h> # define N 2500 int C,L,i,num,SUM,maxSPF; int COW[2][N],LFS[2][N],tree[N]; void change(int *A,int *B) { int C=*A; *A=*B; *B=C; } void insert(int Tree[],int X) { int par,i=++Tree[0]; while(i>1) { par=i/2; if(Tree[par]<=X) break; Tree[i]=Tree[par]; i=par; } Tree[i]=X; } int DelMin(int Tree[]) { int i=1,root=Tree[1],R,L,X=Tree[Tree[0]--]; if(Tree[0]<0) return -1; while(i*2<=Tree[0]) { L=i*2; R=L+1; if(R<=Tree[0]&&Tree[R]<Tree[L])L=R; if(Tree[L]>=X) break; Tree[i]=Tree[L]; i=L; } Tree[i]=X; return root; } void paixu(int A[][N],int left,int right) { int i=left,j=right,temp=A[0][left]; if(left>right) return; while(i!=j) { while(A[0][j]>=temp && i<j)j--; while(A[0][i]<=temp && i<j)i++; if(i<j) { change(&A[0][i],&A[0][j]); change(&A[1][i],&A[1][j]); } } change(&A[0][left],&A[0][i]); change(&A[1][left],&A[1][i]); paixu(A,left,i-1); paixu(A,i+1,right); } int main(){ scanf("%d %d",&C,&L); for(i=0;i<C;i++) scanf("%d %d ",&COW[0][i],&COW[1][i]); paixu(COW,0,C-1); for(i=0;i<L;i++) scanf("%d %d ",&LFS[0][i],&LFS[1][i]); paixu(LFS,0,L-1); for (i=0;i<L;i++) { while (num<C&&COW[0][num]<=LFS[0][i]) insert(tree,COW[1][num++]); while (tree[0]&&LFS[1][i]) { if (DelMin(tree)>=LFS[0][i]) { ++SUM; --LFS[1][i]; } } } printf("%d\n",SUM); return 0; }

运行结果2:

ResultMemoryTimeLanguageCode lengthAccepted208KB72MSC1512B

代码<C语言>用了选择排序 差距挺大的:

# include <stdio.h> # define N 2500 void insert(int Tree[],int X);//最小堆 向Tree堆里插入X tree[0]用来记录当前堆中数的个数 int DelMin(int Tree[]);//最小堆 删除最小值 tree[0]用来记录当前堆中数的个数 void paixu(int A[][N],int n);//以A[0]为比较依据 升序 void change(int *A,int *B);//交换A B的值 int main(){ int C,L,i,num=0,SUM=0,maxSPF; int COW[2][N]={0},LFS[2][N]={0},tree[N]={0}; scanf("%d %d",&C,&L); for(i=0;i<C;i++) scanf("%d %d ",&COW[0][i],&COW[1][i]);//&COW[0][i],&COW[1][i] 分别存储牛的min max光 for(i=0;i<L;i++) scanf("%d %d ",&LFS[0][i],&LFS[1][i]);//LFS[0] LFS[1]分别存储防晒霜的 SPF 与瓶数 paixu(COW,C);//按照牛的mini生序 paixu(LFS,L);//按照化妆品的SPF升序 for (i=0;i<L;i++) { //num为当前选中的满足可以涂防晒霜的牛 while (num<C&&COW[0][num]<=LFS[0][i])//选出符合第i瓶防晒霜的牛 insert(tree,COW[1][num++]);//进堆 while (tree[0]&&LFS[1][i]) { if (DelMin(tree)>=LFS[0][i])// “maxi”比这一瓶的上限大，说明这头奶牛可以被涂上防晒霜 { ++SUM; --LFS[1][i]; } } } printf("%d\n",SUM); return 0; } void insert(int Tree[],int X)//向Tree堆里插入X { int par,i=++Tree[0]; //插入X 后 Tree[0]+1 while(i>1) //直到i不是根节点 { par=i/2; //父节点为par if(Tree[par]<=X) break;//如果父节点满足最大堆的特性 则插入当前的位置即可 Tree[i]=Tree[par]; //否则调整堆 即位置上移 i=par; } Tree[i]=X;//插入新节点 } int DelMin(int Tree[])//删除最小值 { int i=1,root=Tree[1],R,L,X=Tree[Tree[0]--];//X记录当前末尾节点 root为根 即为最小值 if(Tree[0]<0) return -1; while(i*2<=Tree[0]) { L=i*2; R=L+1;//Left Right 记录左右节点 if(R<=Tree[0]&&Tree[R]<Tree[L])L=R; if(Tree[L]>=X) break;//如果所有的位置已经调整好 跳出循环 Tree[i]=Tree[L];//否则继续调整堆 i=L; } Tree[i]=X; return root; } void paixu(int A[][N],int n)//以A[0]为比较依据 升序 { int i,j,k; for(i=0;i<n-1;i++) { k=i; for(j=i+1;j<n;j++) if(A[0][j]<A[0][k]) k=j; if(k!=i) { change(&A[0][i],&A[0][k]); change(&A[1][i],&A[1][k]); } } } void change(int *A,int *B)//交换A B的值 { int C=*A; *A=*B; *B=C; }