求助倒数第二个点过不了
查看原帖
求助倒数第二个点过不了
115298
一嘟噜肉楼主2021/3/10 14:13

我的思路是这样的:在二分的基础上,加一个max_l记录可以切成k段的最大绳子长度,然后也考虑了mid=0的情况,但是倒数第二个点一直过不了

#include <bits/stdc++.h>

using namespace std;

#define maxn 10005

int n,k;
int l[maxn];
double input[maxn];

bool judge(int x){
    int ans=0;
    for(int i=0;i<n;i++){
        ans+=l[i]/x;
    }
    return ans>=k;
}

int main(){
    scanf("%d%d",&n,&k);
    int max_l=0;
    for(int i=0;i<n;i++){
        scanf("%lf",&input[i]);
        l[i]=input[i]*100;
        max_l=max(l[i],max_l);
    }
    sort(l,l+n);
    int left=0,right=max_l;
    int max_ans=0;
    int mid=0;

        while(left<=right){
            int ans=0;
            mid=(left+right)/2;
            if(mid==0){
                printf("0.00");
                break;
            }
            for(int i=0;i<n;i++){
                ans+=l[i]/mid;
            }
            if(ans<k)//绳子少了,说明绳子要短一点
                right=mid-1;
            else if(ans>k)//绳子多了,说明绳子要长一点
                left=mid+1;
            else if(ans==k){
                //如果可以切成k段,那就记录当前mid值
                max_ans=max(max_ans,mid);
                left=mid+1;
            }

        }

        if(max_ans==0&&mid){
            printf("%.2lf",l[n-k]/100.0);
        }
        else if(max_ans!=0&&mid){
            printf("%.2lf",max_ans/100.0);
        }
  }
2021/3/10 14:13
加载中...