《算法》枚举算法作业(四)

时间限制 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;

}

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 时间限制 1000 ms内存限制 64 MB题目描述有一条河,河中间有一些石头,已知石头的数量和相邻两块石头之间的...
    续袁阅读 2,132评论 0 0
  • 时间限制 1000 ms内存限制 64 MB题目描述给你一个长度为n的数组和一个正整数k,问从数组中任选两个数使其...
    续袁阅读 1,283评论 0 0
  • 时间限制 1000 ms内存限制 64 MB题目描述李老师正准备暑假旅行,他有一个容量为L的行李箱和n个物品(n不...
    续袁阅读 1,454评论 0 1
  • 马上过中秋了。我们也放假啦。我希望过一个快快乐乐的中秋节。
    田博学阅读 215评论 0 0
  • 如果你现在的生活有点混乱,有点迷茫,或者不知所措,先不要什么职业规划,个人定位,做个行动派。先从简单的行动做起,从...
    坚持Benoy阅读 158评论 0 1