您现在的位置是:首页 > 学习之路 > ACM||算法ACM||算法

二分法 | 简单的概念进行叠加

卞振伟2018-12-17【ACM||算法】人已围观

简介简单的概念进行叠加 ———— 李笑来文章

二分法,有多难呢?没多难。可是,叠加使用就是需要学和练的了。
我要把这二分法,使用到100遍以上。没有100遍,就不能说自己熟练掌握了这个工具。

你可能在想,,,为什么没有C语言,,,Java,,,或者python版的

而且作为一个解析---->居然没有注释---->(  蒟蒻的我表示根本看不懂(哭笑) )

emmm本来是要弄得,,,但是

弄了一晚上代码高亮,,,心累。。。凑活着看吧

 

第一题:


月度开销

描述

 

农夫约翰是一个精明的会计师。他意识到自己可能没有足够的钱来维持农场的运转了。他计算出并记录下了接下来 N (1 ≤ N ≤ 100,000) 天里每天需要的开销。 约翰打算为连续的M (1 ≤ M ≤ N) 个财政周期创建预算案,他把一个财政周期命名为fajo月。每个fajo月包含一天或连续的多天,每天被恰好包含在一个fajo月里。 约翰的目标是合理安排每个fajo月包含的天数,使得开销最多的fajo月的开销尽可能少。

输入

 

第一行包含两个整数N,M,用单个空格隔开。 接下来N行,每行包含一个1到10000之间的整数,按顺序给出接下来N天里每天的开销。

输出

 

一个整数,即最大月度开销的最小值。

输入样例 1 

    7 5
    100
    400
    300
    100
    500
    101
    400

输出样例 1

500

提示

若约翰将前两天作为一个月,第三、四两天作为一个月,最后三天每天作为一个月,则最大月度开销为500。其他任何分配方案都会比这个值更大。

 
#include <iostream>
using namespace std;

const int maxn=1e5+10;
int n,m,arr[maxn];

bool check(int x)
{
    int sum=0,cot=1;
    for(int i=0; i<n; ++i)
    {
        sum+=arr[i];
        if(sum>x)
        {
            cot++;
            sum=arr[i];
        }
    }
    return (cot<=m)?1:0;
}

int main()
{
    cin>>n>>m;
    int l,r=l=0;
    for(int i=0; i<n; ++i)
    {
        cin>>arr[i];
        r+=arr[i];
        l=max(l,arr[i]);
    }
    int ans;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(check(mid))
        {
            ans=mid;
            r=mid-1;
        }
        else
        {
            l=mid+1;
        }
    }
    cout<<ans;
}
 

第二题:

分巧克力

描述

 

儿童节那天有K位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。 小明一共有N块巧克力,其中第i块是Hi x Wi的方格组成的长方形。

为了公平起见,小明需要从这 N 块巧克力中切出K块巧克力分给小朋友们。切出的巧克力需要满足:

1. 形状是正方形,边长是整数  
2. 大小相同  

例如一块6x5的巧克力可以切出6块2x2的巧克力或者2块3x3的巧克力。

当然小朋友们都希望得到的巧克力尽可能大,你能帮小Hi计算出最大的边长是多少么?

输入

 

输入第一行包含两个整数N和K。(1 <= N, K <= 100000)
以下N行每行包含两个整数Hi和Wi。(1 <= Hi, Wi <= 100000) 输入保证每位小朋友至少能获得一块1x1的巧克力。

输出

 

输出输出切出的正方形巧克力最大可能的边长。

输入样例 1 

2 10  
6 5  
5 6 

输出样例 1

2
 
#include<iostream>
using namespace std;

const int maxn=1e5+10;
int n,k,hi[maxn],wi[maxn];

bool check(int x)
{
    int sum=0;
    for(int i=0; i<n; ++i)
    {
        sum+=(hi[i]/x)*(wi[i]/x);
    }
    if(sum>=k)  return 1;
    return 0;
}


int main()
{
    cin>>n>>k;

    int Max=0,l=0,r=Max,ans;

    for(int i=0; i<n; ++i)
    {
        cin>>hi[i]>>wi[i];
        Max=max(max(hi[i],wi[i]),Max);
    }

    while(l<=r)
    {
        int mid=(l+r)/2;
        if(check(mid))
        {
            ans=mid;
            l=mid+1;
        }
        else
        {
            r=mid-1;
        }
    }
    cout<<ans;
}
 

第三题:

分巧克力

描述

 

儿童节那天有K位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。 小明一共有N块巧克力,其中第i块是Hi x Wi的方格组成的长方形。

为了公平起见,小明需要从这 N 块巧克力中切出K块巧克力分给小朋友们。切出的巧克力需要满足:

1. 形状是正方形,边长是整数  
2. 大小相同  

例如一块6x5的巧克力可以切出6块2x2的巧克力或者2块3x3的巧克力。

当然小朋友们都希望得到的巧克力尽可能大,你能帮小Hi计算出最大的边长是多少么?

输入

 

输入第一行包含两个整数N和K。(1 <= N, K <= 100000)
以下N行每行包含两个整数Hi和Wi。(1 <= Hi, Wi <= 100000) 输入保证每位小朋友至少能获得一块1x1的巧克力。

输出

 

输出输出切出的正方形巧克力最大可能的边长。

输入样例 1 

2 10  
6 5  
5 6 

输出样例 1

2
#include<iostream>
#include<math.h>
#include<cstdio>
using namespace std;

int T,Y;

bool check(double x)
{
    double res = 8*pow(x,4.0)+7*pow(x,3.0)+2*x*x+3*x+6;
    if( res <= Y )
        return 1;
    return 0;
}

int main()
{
    cin>>T;
    while(T--)
    {
        cin>>Y;
        double l=0,r=100,ans;
        double item = 8*pow(100,4.0)+7*pow(100,3.0)+2*100*100+3*100+6;
        if(check(0) && Y<=item )
        {
            while(1e-6 <= r-l)
            {
                double mid=(l+r)/2;
                if(check(mid))
                {
                    ans=mid;
                    l=mid+1e-7;
                }
                else
                {
                    r=mid-1e-7;
                }
            }
            printf("%.4f\n",ans);
        }
        else
        {
            printf("No solution!\n");
        }
    }
}

Tags:ACM   编程   个人   题解   算法   C|C++

很赞哦! ()

文章评论

站点信息

  • 建站时间:2018-11-25
  • 网站程序:帝国CMS7.5
  • 文章统计:118篇文章
  • 标签管理标签云
  • 统计数据百度统计
  • 网站地图XML网站地图
  • 微信公众号:扫描二维码,关注我的公众号
  • GitHub:扫描二维码,关注我的GitHub

客服在线

QQ客服

客服微信扫码

服务时间

周一至周日 9:00-21:00