枚举算法作业（四）

时间限制 1000 ms
内存限制 64 MB
题目描述
我们有n根的木棍。现在从这些木棍中切割出来m条长度相同的木棍，问这m根木棍最长有多长？

输入数据
第一行输入两个数字，n(1<=n<=1000)为木棍数目，m(1<=m<=1000)为需要切割出的相同长度的木棍数目 随后n个正整数，表示原始木棍的长度(<=10000)

输出数据
每组输出一行结果，表示切割后绳子的最长长度(保留两位小数)

样例输入
4 5
5 6 7 8
样例输出
4.00

方法一

#include<stdio.h>
#include<math.h>
#include<iomanip>
#include "stdlib.h"
#include <iostream>
using namespace std;

int main(){
    int m, n;
    int *a;
    cin >> n >> m;
    a = (int *)malloc(sizeof(int) * n); // 分配
    for (int i = 0; i<n; i++)
    {
        cin >> a[i]; // 键盘输入 n 个数
    }
    float max_length = a[0];        //临时变量
    for (int i = 1; i < n-1; i++)
    {
        
        if (max_length<a[i])
            max_length = a[i];
    }
    //cout << "max_length:" << max_length << endl;


    while (max_length>0){
        int count = 0;
        for (int i = 0; i < n; i++){
            count = count + floor(a[i] / max_length);
            
        }
        //cout << "count：" << count << endl;
        if (count == m){
            //cout <<"结果："<< max_length << endl;
            cout << setiosflags(ios::fixed) << setprecision(2) << max_length << endl;
            return 1;
            //break;
        }
        else{
            //cout << "过程：" << min_length << endl;
            max_length = max_length - 0.01;
            max_length = round(max_length * 100) / 100.0;
            //cout << "过程：" << max_length << endl;
            //cout << setiosflags(ios::fixed) << setprecision(2) << max_length << endl;
        }

    }

    return 0;

}

方法二

#include<stdio.h>
#include<math.h>
#include<iomanip>
#include "stdlib.h"
#include <iostream>
using namespace std;

int main(){
    int m, n;
    int *a;
    cin >> n >> m;
    a = (int *)malloc(sizeof(int) * n); // 分配
    for (int i = 0; i<n; i++)
    {
        cin >> a[i]; // 键盘输入 n 个数
    }
    float max_length = a[0];        //临时变量
    for (int i = 1; i < n; i++)
    {
        if (max_length<a[i])
            max_length = a[i];
    }
    //cout << "max_length:" << max_length << endl;

    double left = 0, right = max_length, mid;
    while (left +0.01 < right){
        int num = 0;
        mid = (left + right) / 2.00;
        //cout << "mid" <<mid<< endl;
        mid = round(mid * 100) / 100.0;
        //cout << "---mid---" << mid << endl;
        for (int i = 0; i<n; i++){
            num += floor(a[i] / mid);
        }
        if (num >= m){
            left = mid;
        }
        else{
            right = mid;
        }
    }

    cout << setiosflags(ios::fixed) << setprecision(2) << left << endl;
    return 0;

}