公园长凳

问题描述

公园有 x 条长凳。第 i 个长凳上坐着 ai 个人。这时候又有 y 个人将来到公园，他们将选择坐在某些公园中的长凳上，那么当这 y 个人坐下后，记 k = 所有椅子上的人数的最大值，那么 k 可能的最大值 mx 和最小值 mn 分别是多少。

Input

第一行包含一个整数 x (1 ≤ x ≤ 100) 表示公园中长椅的数目
第二行包含一个整数 y (1 ≤ y ≤ 1000) 表示有 y 个人来到公园
接下来 x 个整数 ai (1 ≤ ai ≤ 100)，表示初始时公园长椅上坐着的人数

Output

输出 mn 和 mx

Sample

Input: 
3
7
1
6
1

Output: 
6 13

Explain:
最初三张椅子的人数分别为 1 6 1
接下来来了 7 个人。
可能出现的情况为 {1, 6, 8}, {1, 7, 7}, …, {8, 6, 1}
相对应的 k 分别为 8, 7, …, 8
其中，状态 {1, 13, 1} 的 k = 13，为 mx
状态 {4, 6, 5} 和状态 {5, 6, 4} 的 k = 6，为 mn

Limitation

Time limit		1000 ms
Memory limit	262144 kB

解题思路

咋一看，貌似挺简单，直接对 x_i 排序，则 mx = x_max + y，mn = x_min + y，太简单了……后来写着写着猛地发现想错了，去看了下样例解释：emm，原来没那么简单。

不过mx求法挺简单的，就是 mx = x_max + y，mn 麻烦了点而已。

不难发现，x_i 排序后可以看作非减的一排柱形图，可以用 y (分割成 n 个部分)对其填充，记 temp = 所有柱子填充成最高柱子所需的量，则有两种情况：y 够分配给 temp；y 不够分配给 temp。如下图所示：

对于 y ≤ temp，则 mn = x_max；对于 y > temp，mn = x_max + ⌈超出部分/x⌉。

所以这题也不难啊。

不过WA了一次，原因是我没对差值结果/x取double再取ceil，而是直接int取ceil，相当于没取ceil，没用。

源代码

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
	int x, y;
	cin >> x >> y;
	vector<int> v;
	for(int i = 0; i < x; i++) {
		int a;
		cin >> a;
		v.push_back(a);
	}
	sort(v.begin(), v.end());
	int theMAX = v[v.size() - 1];
	int mn, mx;
	mx = y + theMAX;
	
	int temp = 0;
	for (int i = 0; i != v.size(); i++)
		temp += (theMAX - v[i]);

	if (temp >= y)
		mn = theMAX;
	if (temp < y) {
		int overFlow = y - temp;
		int incrs = ceil((double) overFlow / x);
		mn = theMAX + incrs;
	}
	cout << mn << " " << mx << endl;
	return 0;
}