一个疑问
  • 板块P1577 切绳子
  • 楼主SJZ2010
  • 当前回复5
  • 已保存回复5
  • 发布时间2023/7/13 13:21
  • 上次更新2023/11/3 10:08:31
查看原帖
一个疑问
809729
SJZ2010楼主2023/7/13 13:21

这是我原来的代码(77pts77 pts)

#include <iostream>
#include <cstdio>

int n, k;
double l[10005];

bool check(int x){
    int ans=0;
    for(int i=1;i<=n;i++)
        ans+=(int)l[i]/x;
    return ans<k;
}
int main(){
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
    std::cin >> n >> k;
    for(int i=1;i<=n;i++)
        std::cin >> l[i],l[i]=(int)(l[i]*10000);
    int l=0, r=1000000000, mid;
    while(l<=r){
        mid=(l+r)/2;
        if(!mid)
            break;
        if(check(mid))
            r=mid-1;
        else
            l=mid+1;
    }
    printf("%.2lf",l/10000.0);
    return 0;
}

然后我翻了一下讨论区,改了一点点后试了一发,居然过了

#include <iostream>
#include <cstdio>

int n, k;
double l[10005];

bool check(int x){
    int ans=0;
    for(int i=1;i<=n;i++)
        ans+=(int)l[i]/x;
    return ans>=k;
}
int main(){
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
    std::cin >> n >> k;
    for(int i=1;i<=n;i++)
        std::cin >> l[i],l[i]=(int)(l[i]*10000);
    int l=0, r=(1<<30), mid;
    while(l<=r){
        mid=(l+r)/2;
        if(!mid)
            break;
        if(check(mid))
            l=mid+1;
        else
            r=mid-1;
    }
    printf("%.2lf",l/10000.0-0.004);
    return 0;
}

而这只是在最后的输出上有小改动,为什么就过了呢?

我猜测这个二分大概是答案偏向于右侧的值 (r)的,不知道有没有更合理的解释,求大佬解答

2023/7/13 13:21
加载中...