點擊打開鏈接

百度一共制造了 $n$ 輛無人車，其中第 $i$ 輛車的重量為 ai?kga_i\ \mathrm{kg}ai??kg。

由于車輛過重會增大輪胎的磨損程度，現在要給這 $n$ 輛車減輕重量。每將一輛車減輕 $1\mathrm{k}\mathrm{g}$ 需要消耗 $p$ 萬百度幣，總預算為 $s$ 萬百度幣。

現在希望你設計一種最優的減重方案，使得最重的車輛的重量是所有減重方案中最小的。任何時候，每輛車的重量必須大于等于 $1\mathrm{k}\mathrm{g}$。并且減重方案只能減輕整數 $\mathrm{k}\mathrm{g}$。

輸入格式

第一行輸入一個整數 $n$，表示百度無人車的數量。

接下來一行輸入 $n$ 個整數，其中第 $i$ 個整數 aia_iai? 表示第 $i$ 輛車的重量。

接著一行輸入兩個整數 $p,s$，分別表示把一輛車減重 $1\mathrm{k}\mathrm{g}$ 需要花費 $p$ 萬百度幣，總的預算是 $s$ 萬百度幣。

保證 $1\le n\le 20000$，1≤ai≤200001 \le a_i \le 200001≤ai?≤20000，$1\le p\le 20000$，1≤s≤10181 \le s \le 10^{18}1≤s≤1018。

輸出格式

輸出一個整數，表示經過你設計的最優減重方案后，最重的車輛的重量是多少 $\mathrm{k}\mathrm{g}$。

樣例輸入1

4 6 7 8 9 1 3

樣例輸出1

7

樣例輸入2

5 11 14 6 13 11 4 68

樣例輸出2

8

分析：

先把n個數從小到大排序，然后計算差分數組：b[I]=a[I]-a[l-1];

從后向前掃描差分數組，如果當前預算足夠減去這一層，則b[l]=0，更新s;

否則把全部預算用用于減輕重量，b[l]更新為減輕后的值，跳出循環

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=2e4+10; int n,p,a[maxn]; ll s; int b[maxn];//差分數組 int main() {scanf("%d",&n);for(int i=0;i<n;i++)scanf("%d",&a[i]);scanf("%d%lld",&p,&s);sort(a,a+n);b[0]=a[0];for(int i=1;i<n;i++)//計算差分數組b[i]=a[i]-a[i-1];s=s/p;//這些預算可以減輕多少kg /*for(int i=0;i<n;i++)cout<<b[i]<<endl; */int k=1;//代表這是從后往前數第k輛車for(int i=n-1;i>=0;i--){if(s>=b[i]*k){//當前預算足夠減輕重量s-=b[i]*k;b[i]=0;}else{//預算不夠，把全部預算用完int t=b[i]*k-s;b[i]=ceil(1.0*t/k);//浮點數向上取整s=0;break;}k++;}ll ans=0;if(b[0]<1)//最小重量為1kgprintf("1\n");else{//差分數組求和for(int i=0;i<n;i++){//cout<<b[i]<<endl;ans+=b[i];}printf("%lld\n",ans);}return 0; }

總結

以上是生活随笔為你收集整理的计蒜客 百度无人车的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。