欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

切香肠(二分答案+贪心)

程序员文章站 2022-03-11 23:29:59
...

切香肠(二分答案+贪心)
当初没想到二分,单纯暴力,结果tle。。。

题解

题目说1单位长度可分为100份,所以我们可以去放大100倍(乘以100),将小数转为整数去做,可避免精度误差的问题,当然直接小数去做也是可以的。接下来就在一个区间里面二分寻找最大的答案即可。

Code

①转化为整数去二分

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,k,a[100005];
bool check(int u)
{
    if(!u)return true;
    ll w=0;
    for(int j=0;j<n;j++){
        w+=a[j]/u; /*要考虑u可能是0时的情况,所以要特判0*/
        if(w>=k)return true;
    }
    return false;
}
int main()
{
    double q;
    scanf("%lld%lld",&n,&k);
    for(int i=0;i<n;i++){
        scanf("%lf",&q);
        a[i]=ll(q*100);
    }
    int r=1000000000,l=0,mid;
    while(l<r){ 
        mid=l+((r-l)>>1);
        if(check(mid))l=mid+1;
        else r=mid;
    }
   /*while(l<=r){  //两种写法均可ac
        mid=l+((r-l)>>1);
        if(check(mid))l=mid+1;
        else r=mid-1;
    }*/
    printf("%.2f\n",double(l-1)/100.0);
    return 0;
}

②直接浮点数二分

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const double eps=1e-8;
ll n,k;
double a[100005];
bool check(double u)
{
    ll w=0;
    for(int j=0;j<n;j++){
        w+=(int)floor(a[j]/u);
        if(w>=k)return true;
    }
    return false;
}
int main()
{
    double q;
    scanf("%lld%lld",&n,&k);
    for(int i=0;i<n;i++)
        scanf("%lf",&a[i]);
        
    double r=1e9,l=0;
    
    /*while(r-l>eps){     //两种写法均可ac
        double mid=(l+r)/2.0;
        if(check(mid))l=mid;
        else r=mid;
    }*/
    for(int i=1;i<=60;i++){
        double mid=(l+r)/2.0;
        if(check(mid))l=mid;
        else r=mid;
    }
    
    printf("%.2f\n",(int)floor(r*100.0)/100.0);
    return 0;
}
相关标签: 题解