首页 > 试题广场 >

(切割绳子)有 n 条绳子,每条绳子的长度已知且均为正整数。

[填空题]
(切割绳子)有 n 条绳子,每条绳子的长度已知且均为正整数。绳子可以以任意正整数长度切割,但不可以连接。现在要从这些绳子中切割出 m 条长度相同的绳段,求绳段的最大长度是多少。(第一、二空 2.5 分,其余 3 分)

输入:第一行是一个不超过 100 的正整数 n,第二行是 n 个不超过 106 的正整数,表示每条绳子的长度,第三行是一个不超过 108 的正整数 m。
输出:绳段的最大长度,若无法切割,输出 Failed。

var
  n, m, i, lbound, ubound, mid, count : longint;
  len : array[0..100] of longint;   // 绳子长度 
begin
  read(n);
  count := 0;
  for i := 0 to n - 1 do
  begin
    read(len[i]);
    1;
  end;
  read(m);
  if (2) then
  begin
    writeln('Failed');
    exit;
  end;
  lbound := 1;
  ubound := 1000000;
  while (3) do
  begin
    mid := 4;
    count := 0;
    for i := 0 to n - 1 do
    5;
    if (count < m) then
      ubound := mid - 1
    else
      lbound := mid;
  end;
  writeln(lbound);
end. 

#include<iostream>
#include<cmath>
using namespace std;
bool judge_binary_search(float max_l,int n,int m,int l[]);
int main()
{
    int n,m,l[n];
    cin>>n;
    cin>>m;
    for (int i=0;i<n;i++) cin>>l[i];
    
    float left=0.0;
    float right=l[0];
    float max_l=0.0;
    int num=0;
    for(int i=0; i<n; i++){
        num+=l[i]/l[0];
    }
    if(num==m){
        printf("%.2f",floor(l[0]*100/100));
        return 0;
    }
    while(fabs(left-right)>1e-2){
        max_l=(left+right)/2;
        if(judge_binary_search(max_l,n,m,l)) left=max_l;
        else right=max_l;
    }
    printf("%.2f",floor(max_l*100)/100);
}
bool judge_binary_search(float max_l,int n,int m,int l[]){
    int cut_num=0;
    for(int i=0;i<n;i++){
        cut_num+=l[i]/max_l;
    }
    if(cut_num<=m) return false;
    else if (cut_num>m) return true;
}
发表于 2019-03-16 12:07:20 回复(0)