题目：

  有一个核心交易系统接口被N个上游系统调用，每个上游系统的调用量R=[R1,R2,…,RN]。由于核心交易系统集群故障，需要暂时系统降级限制调用，核心交易系统能接受的最大调用量为cnt。
  设置降级规则如下: 如果sum(R1,R2…RN) 小于等于cnt，则全部可以正常调用，返回-1; 如里sum(R1,R2…RN)大于cnt，设置一个阈值limit，如果某个上游系统发起的调用量超过limlt，就将该上游系统的调用量限制为limit，其余未达到limit的系统可以正常发起调用。
  求出这个最大的limit (limit可以为0)。

输入：

第一行：每个上游系统的调用量 (整型数组)
第二行：核心交易系统的最大调用量

输出：

调用量的阈值limit

样例：

输入:
1 4 2 5 5 1 6
13
输出：2

解释：因为1+4+2+5+5+1+ 6>13; 将limit设置为2，则1+2+2+2+ 2+1+2=12<13，所以limit为2。

输入：
1 7 8 8 10 2 4 9
7
输出：0

解释：因为即使limit设置为1。1+1+1+1+1+1+1+1=8>7也不满足，所以limit只能为0。

思路：

1. 输入一个向量R=[R1,R2,…,RN]，输入最大调用量为cnt；
2. 如果sum(R1,R2…RN) 小于等于cnt，返回-1;
3. 如果sum(R1,R2…RN) 大于cnt，调用函数getlimit(R，cnt)求limit；
   函数本质，找到一个最小的数，使得R经过这个数滤波后，求和值尽可能接近cnt。
   方法一暴力求解：可以先用cnt/N向下取整得到pcnt，如果小于1，则返回0；然后cnt = cnt-n个min(R)，还剩N = N-n个数，继续向下取整更新pcnt，如果大于之前的值则记录。一直遍历完全部的数组。
   方法二：利用二分法和中位数去逼近limit。

方法二代码：（上面这个超int了）

#include <iostream>
#include <vector>
#include <algorithm>
# include<numeric>
using namespace std;int getlimit(vector<int> R, int cnt) {int left = 0;int right = R.size()-1;int limit = R[left];while (left<right) {  // 二分法找到最接近的limitint p = (left + right) / 2;if (accumulate(R.begin(), R.begin() + left, (R.size() - left) * R[left]) < cnt){left = p;}else { right = left; }limit = R[left];}for (int i = 1; i <= R[left]; i++)  // 进一步逼近{if (accumulate(R.begin(), R.begin() + left, (R.size() - left) * limit) > cnt){limit = R[left]-i;}else { break; }}return limit;
}int main()
{int cnt;vector<int> R;while (1) {   // 输入不定长的Rcin >> cnt;R.push_back(cnt);if (cin.get()=='\n') { break; }}cin >> cnt;sort(R.begin(),R.end());int sum = accumulate(R.begin(), R.end(), 0);if (sum <= cnt) { cout << "-1"; }else { int limit = getlimit(R, cnt); cout << limit; }return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {int n;vector<int> R;while (cin >> n) {R.push_back(n);}R.erase(--R.end());int Rsize = R.size();if (Rsize > n) {cout << 0 << endl;return 0;}int maxR = *max_element(R.begin(), R.end());int left = 0, right = maxR;while (left < right) {int mid = left + (right - left + 1) / 2;long long sum = 0;for (int i = 0; i < Rsize; ++i) {if (R[i] < mid) {sum += R[i];}else {sum += mid;}}if (sum <= n) {left = mid;}else {right = mid - 1;}}cout << (left == maxR ? -1 : left) << endl;return 0;
}