2020 蓝桥杯大学模拟赛(三) - 程序设计：分披萨题解

电玩女神 2022-12-28 14:15 138阅读 0赞

### 文章目录 ###

*  题目描述
 *   *  输入格式
     *  输出格式
     *  数据范围
     *  样例输入
     *  样例输出
 *  算法分析
 *  解题代码

--------------------

# 题目描述 #

由于太久没有⻅到朋友们，⼩明这天晚上做了⼀个甜美的梦。

这天⼀共有`n`个同学⼀起聚餐，他们⼀共点了`m`块披萨，每块披萨的⼤⼩不尽相同，分别为 **ai** 。 现在遇到了⼀个尴尬的问题，由于⼩明是⼀个正直的⼈，他希望在场的所有⼈分得的披萨⼀样⼤， 但披萨只能被切成整数⼤⼩，不同的披萨之间也不能拼接。现在他想知道，每个⼈最多能吃到多⼤ 的披萨呢。

## 输入格式 ##

> 第⼀⾏包含两个整数 , 表示有 `n` 个同学和 `m` 块披萨。  
> 接下来⼀⾏ `m` 个数表示每块披萨的⼤⼩。

## 输出格式 ##

> 输出⼀⾏，每个⼈最多能吃到多⼤的披萨。

## 数据范围 ##

![1][]

## 样例输入 ##

4 2
    7 9

## 样例输出 ##

# 算法分析 #

这道题思维需要转化一下，如果按照一般贪心的想法，将每种披萨都对于每一个同学平分，这样可以保证公平性，每个同学都分到一样大的披萨，但是这种方法得出的最大披萨数是不正确的。

因为每种披萨是不能拼接的，也就意味着考虑每个人吃到的披萨都是某一种披萨的最大。

**那怎么保证某一种披萨的最大呢。**

我们换个思维，先保证某一种披萨的最大值，再保证每个同学的公平性。

那么就可以使用二分的思想，二分披萨的最大值，然后去验证在这个披萨的最大值下，能不能保证公平性，使得每个同学都能分到这么大的披萨

# 解题代码 #

#include <iostream>
    using namespace std;
    
    int pizze[100005];
    int n,m;
    
    bool check(int mid)
    {
        
      	//验证在当前披萨大小下，能否给每个同学都分到这么大
        int temp = 0;	//记录当前大小下，能分给多少个同学
        for(int i = 0; i < m; i++)
            temp += pizze[i] / mid;
        
        if(temp >= n) return true;
        else
            return false;
    }
    
    int main()
    {
        
        cin >> n >> m;
        
        for(int i = 0; i < m; i++)
            cin >> pizze[i];
        
      	//二分披萨的最大值的大小
        int l = 0, r = 1000005;
        int mid = 0;
        while(l <= r){
        
            int mid = (l + r) >> 1;
            if(check(mid))
                l = mid + 1;
            else
                r = mid - 1;
        }
        
        cout << r << endl;
      
      	return 0;
    }

[1]: /images/20221120/7644d29feeff4c0ba7cf29de4e4ded20.png