题解 P1577 【切绳子】

原题连接P1577 切绳子

首先这是一道很常规的二分题看标签就知道了

思路很常规，二分答案贪心判断

首先假设第\(i\)个绳子长度为\(a[i]\)呢么这条绳子说能切割出的绳子条数为$\frac {a[i]} {mid} $,求和判断一下就好了

看到这里你是不是觉得写完了

不 \(o(>﹏<)o\) 这道题卡精度，想不到吧！！！

如果你\(85\)分\(WA\)，呢么恭喜\(printf\)四舍五入卡住了您

如果你\(92\)分\(RE\)，呢么恭喜您您的除数出现了\(0\)

呢么我就说说我是怎么解决这两个问题的

第一个，我发现数据很水所以读入时每个数乘\(100\)输出时在除\(100\)就好了

第二个，在二分时加一个 if(!mid) break;

\(85\)分\(WA\) \(coding\)

#include <bits/stdc++.h>
using namespace std;


const double e = 1e-3;
const int N = 10005;
int n,m,cnt;
double a[N] = {},l,r,result;


inline bool check(double k)
{
    cnt = 0;
    for(register int i = 1;i <= n;i ++)
    {
        cnt += a[i]/k;
        if(cnt > m) return 1;
    }
    return cnt >= m;
}


int main()
{
    scanf("%d%d",&n,&m);
    for(register int i = 1;i <= n;i ++)
    {
        scanf("%lf",&a[i]);
        r += a[i];
    }
    r /= m*1.0;
    while(l + e < r)
    {
        register double mid = (r+l)/2;
        if(check(mid)) l = mid,result = mid;
        else r = mid;
    }
    printf("%.2lf\n",result);
    return 0;
}

\(92\)分\(RE\) \(coding\)

#include <bits/stdc++.h>
using namespace std;


const int N = 10005;
int n,m,cnt;
int a[N] = {},l,r = 1 << 30,result;
double num;


inline bool check(int k)
{
    cnt = 0;
    for(register int i = 1;i <= n;i ++)
    {
        cnt += a[i]/k;
        if(cnt > m) return 1;
    }
    return cnt >= m;
}


int main()
{
    scanf("%d%d",&n,&m);
    for(register int i = 1;i <= n;i ++)
    {
        scanf("%lf",&num);
        a[i] = num*100;
    }
    while(l <= r)
    {
        register int mid = (r+l)>>1;
        if(check(mid)) l = mid+1;
        else r = mid-1;
    }
    printf("%.2lf\n",r/100.0);
    return 0;
}

\(ACcoding\)

#include <bits/stdc++.h>
using namespace std;


const int N = 10005;
int n,m,cnt;
int a[N] = {},l,r = 1 << 30,result;
double num;


inline bool check(int k)
{
    cnt = 0;
    for(register int i = 1;i <= n;i ++)
    {
        cnt += a[i]/k;
        if(cnt > m) return 1;
    }
    return cnt >= m;
}


int main()
{
    scanf("%d%d",&n,&m);
    for(register int i = 1;i <= n;i ++)
    {
        scanf("%lf",&num);
        a[i] = num*100;
    }
    while(l <= r)
    {
        register int mid = (r+l)>>1;
        if(!mid) break;
        if(check(mid)) l = mid+1;
        else r = mid-1;
    }
    printf("%.2lf\n",r/100.0);
    return 0;
}