Cpp 数组和结构体

2020-04-03

总阅读量次

问题描述

某位同学邀请k位朋友到家里做客。他拿出了巧克力招待盆友们。他一共有n块巧克力，其中每一块巧克力都是长方形。为了公平起见，这位同学需要从这n块巧克力中分出k块巧克力给盆友们。要求切出的巧克力要满足：
1、形状是正方形，边长是整数，且是一整块。
2、大小相同、朋友分得的巧克力能尽量的大。
请设计算法求出满足要求的最大边长。
（输入n，k，其中1 <= n,k <= 100000,且输入应该保证你的盆友们至少可以分得一块1*1的巧克力）

样例输入：
2 10
6 5
5 6
样例输出：
2

源代码

#include <iostream>

using namespace std;

const int numMax = 50;//规定最多有50块巧克力（可以根据需要指定）

//创建结构体数组，保存用户输入的巧克力的参数
struct{
    int width;
    int height;
    int area;
}cho[numMax];

int main()
{
    int n,k;
    cout << "please input the amount of your chocolates:" << endl;
    cin >> n;
    cout << "please input the amount of your friends:" << endl;
    cin >> k;
    int minLength;
    //接受用户的输入，同时计算出每块巧克力的大小，并求出可以切割的最大边长
    for(int i =0;i<n;i++){
        cout << "please input the " << i+1 << " width and height:" << endl;
        cin >> cho[i].width >> cho[i].height;
        cho[i].area = cho[i].height * cho[i].width;
        int temp = cho[i].height > cho[i].width ? cho[i].width : cho[i].height;
        if(i == 0){
            minLength = temp;
        }
        else{
            minLength = minLength > temp ? minLength : temp;
        }

    }

    cout << "maximum length is : ";

    bool flag = true;
    //从获得的最大边长进行遍历，求得满足所有要求的最大边长
    while(flag){
        int counts = 0;
        for(int i=0;i<n;i++){
            counts += cho[i].area / (minLength*minLength);
            if(counts >= k){
                flag = false;
            }
        }
        if(flag == true && (minLength--) == 1)
            break;
    }
    cout << minLength;

    return 0;
}

测试样例

test1:

test2:

test3: