47.徒步（广赋张老师的题解）

#include <bits/stdc++.h>
using namespace std;
long long a[200005];
int main(){
	int n, k, c;
	cin >> n >> k >> c;			//n种职业，每小队有k人，每队中每种职业可同时有c人
	long long sum = 0;				//总人数sum 
	for (int i = 1; i <= n; i++){	//输入每种职业的人数，例如1号职业有2人，2号职业有3人，3号职业有4人 
		cin >> a[i];
		sum += a[i];				//统计总人数sum 
	}
	
	sort(a + 1, a + 1 + n);		//排序 ，对数组a指定的范围里进行排序(从小到大)，以便后续操作 
	//for (int i = 1; i <= n; i++){cout<<a[i];}cout<<endl;	//测试输出  
	
	long long small = 0, big = sum/k+1;	//两个指针，最少队伍数small，最大队伍数big
	long long mid;						//中间队伍数mid，每次猜中间
	while (small + 1 < big){		//二分法，条件循环，用两个指针从两侧逐渐逼近答案，直到两个指针碰撞就找到了正确答案 
		mid = (small + big)/2;		//中间队伍数mid，每次猜中间
		long long people = 0;						//人数people 
		for (int i = 1; i <= n; i++){	//遍历，从每种职业挑选人，累加到选用人数people 
			people += min(a[i], mid * c);		//选用人数people累加：最小值(当前职业人数，中间队伍数mid*每队每种职业可许人数c) 
			//例如a[2]职业有10人，mid队伍有4队，每队每种职业可许c=3人，所以需要用12人，但实际上只有10个人可以用，所以people增加10人。
			//例如a[3]职业有17人，mid队伍有4对，每队每种职业可许c=3人，所以需要用12人，所以people增加12人，a[3]职业剩余5人就不用了。
		}
		if (people >= k * mid){	//如果选用人数people>=每队人数*中间队伍数（mid支队需要的人数），说明mid猜小了，答案大于mid，
			small = mid;					//最少队伍数small=中间队伍数，small向右移，因为结果还可能更大，进入下一次循环以逼近结果 
		}
		else{					//如果选用people>=每队人数*中间队伍数（mid支队需要的人数），说明mid猜小了，答案小于mid，big向左移 
			big = mid;						//最大队伍数big=中间队伍数，big向左移，因为结果还可能更小，进入下一次循环以逼近结果
		}
	}
	cout << small;
}