P1099 专业多种解法

1.

题意简单来说，就是在一串数中取最少的数，使取的数和大于等于给定数。

这道题是贪心，先选最大的数（即最高的奶牛），一定能使取的数的数目（即奶牛数）最小

如下是证明：

在序列a_1,a_2,……a_n（a_1>=a_2>=a_3……>=a_n）中

若有k个数a_i1,a_i2,a_i3,a_i4……a_ik（i1>i2>i3……>ik,且i1,i2……ik为1～n之间的整数) a_i1+……+a_ik>=h

因为i1>i2>i3……>ik,且i1,i2……ik为1～n之间的整数

所以 i1>=1 i2>=2 …… ik>=k

所以 a_i1<=a_1 a_i2<=a_2 …… a_ik<=a_k

则 a_1+……+a_k>=a_i1+……+a_ik>=h

所以 先选最大的数（即最高的奶牛），一定能使取的数的数目（即奶牛数）最小

那我们下一步就是排序了

在这里我介绍几种较快的做法

#include<cstdio>
#include<queue>
using namespace std;    
int t[10001];    
int main()
    {        
int n,h,hi,i,ans=0;        
scanf("%d %d",&n,&h);        
for(i=0;i<n;i++)            
scanf("%d",&hi),t[hi]++;        
for(i=10000;h>0;i--)
        {            
if (i*t[i]<=h) h-=i*t[i],ans+=t[i];            
else ans+=h/i+1,h=0;
        }        
printf("%d",ans);        
return 0;
    }

桶排，由于数据规模小，这里可以用桶排。

#include<cstdio>
#include<algorithm>
using namespace std;    
int w[20000];    
int main()
{        
int n,h,i;        
scanf("%d %d",&n,&h);       
for(i=0;i<n;i++) 
scanf("%d",&w[i]);
sort(w,w+n);        
for(i=n-1;h>0;i--) h-=w[i];        
printf("%d",n-i-1);        
return 0;
}

快排，用的是模板快排，注意这里默认是从小到大排序。

#include<cstdio>
#include<queue>
using namespace std;
priority_queue <int> que;    
int main()
{        
int n,h,i,hi;        
scanf("%d %d",&n,&h);        
for(i=0;i<n;i++)            
scanf("%d",&hi),que.push(hi);        
for(i=0;h>0;i++)
        {
            h-=que.top();
            que.pop();
        }        
printf("%d",i);        
return 0;
}

堆排，这里用的是STL的优先队列，默认大根堆，在需要数较小时比快排快。

2.思路：从题面分析可得，每次需要找最高的一头奶牛，当“奶牛塔”的高度>=书架高度时即为答案。因为该题局部最优解就是全局最优解，并且有后无效性，所以该题直接sort+贪心+模拟就可以。

#include<bits/stdc++.h> //万能头文件
#define mmax 100000 //奶牛个数在0到10005之间，直接开大一点到100000
using namespace std;
long long n,b,a[mmax],ans,cnt; //因为奶牛的高度在0到2,000,000,007之间，int会爆炸，所以用long longint main(){    scanf("%lld%lld",&n,&b);  //读入
    for(int i=1;i<=n;i++)        
    scanf("%lld",&a[i]); //读入
    sort(a+1,a+n+1,greater<long long>()); //sort快排，虽然不稳定但是方便233，greater<long long>()是从大到小排序
    for(int i=1;i<=n;i++)
      {
          cnt+=a[i]; //贪心开始，每次让最高的奶牛上奶牛塔
          ans++; //奶牛数+1
          if(cnt>=b) //如果奶牛塔高度>=书架高度，停止循环，不让其他奶牛上奶牛塔
          break; //停止循环
      }    
    printf("%lld",ans); //输出答案
    return 0;
}

3.快排，然后从高到矮一个一个把身高加起来直到总高度>=B即可。

#include <bits/stdc++.h>
using namespace std;
int s=0,n,b,h[20001];//定义变量
int main()
{    
    cin>>n>>b;    
    for(int i=1;i<=n;i++)        
    scanf("%d",&h[i]);//输入
    sort(h+1,h+n+1);//快排
    for(int i=n;i>=1;i--)//从高到矮
    {
        s+=h[i];        
        if(s>=b)//达到高度
        {            
            cout<<n-i+1;//输出奶牛只数
            break;
        } 
    }    
   return 0;
}