2018 计蒜之道 初赛 第一场-百度无人车

题目链接

百度一共制造了 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;
}
全部评论

相关推荐

牛客618272644号:佬携程工作怎么样,强度大吗
点赞 评论 收藏
分享
Bug压路:老哥看得出来你是想多展示一些项目,但好像一般最多两个就够了😂页数一般一页,多的也就2页;这些项目应该是比较同质化的,和评论区其他大佬一样,我也觉得应该展示一些最拿手的(质量>数量)😁😁😁专业技能部分也可以稍微精简一些
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务