POJ3614-Sunscreen

Description

Input

Output

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:

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

# 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:

代码<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;
}