题目链接
百度一共制造了 n 辆无人车，其中第 ii辆车的重量为ai kg。 由于车辆过重会增大轮胎的磨损程度，现在要给这 n辆车减轻重量。每将一辆车减轻 1kg需要消耗 p万百度币，总预算为 s万百度币。 现在希望你设计一种最优的减重方案，使得最重的车辆的重量是所有减重方案中最小的。任何时候，每辆车的重量必须大于等于1 kg。并且减重方案只能减轻整数kg。
输入格式 第一行输入一个整数 n，表示百度无人车的数量。
接下来一行输入 n个整数，其中第 i个整数表示第 i辆车的重量。
接着一行输入两个整数 p, s分别表示把一辆车减重 kg 需要花费 p万百度币，总的预算是 s 万百度币。 1<=p<=20000,1<=ai<=20000,1<=s<=十的十八次方 输出格式 输出一个整数，表示经过你设计的最优减重方案后，最重的车辆的重量是多少 kg。 样例输入 4 6 7 8 9 1 3 样例输出 7 样例输入 5 11 14 6 13 11 4 6 8 样例输出 8 题目来源 2018 计蒜之道 初赛 第一场; 题意：
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstdio> using namespace std; const int maxn=20000+100; typedef long long ll; ll n; ll a[maxn]; ll p,s; int main() { cin>>n; ll x; ll j; for(j=0;j<n;j++){ cin>>x; a[x]++; } cin>>p>>s; ll t=s/p; ll i; for(i=20000;i>1;i--){ if(t==0)break; if(a[i]>t)break; a[i-1]+=a[i]; t-=a[i]; } cout<<i<<endl; return 0; }