lalalala


私信TA

用户名:zhangshuo

访问量:5525

签 名:

像狗一样的学习,像绅士一样地玩耍。

排  名 2
经  验 12690
参赛次数 2
文章发表 185
年  龄 11
在职情况
学  校 大官山小学
专  业

  自我简介:

今日懒惰流下的口水,将会成为明日里伤心的泪水。

TA的其他文章

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


  评论区

好文好文,给小白转了~
2018-03-22 08:47:25 | |
  • «
  • 1
  • »