最优河堤加固方案(C++/Py/Java/Js/Go)题解

华为笔试真题 7月24号 非AI方向第一题 100分题型

题目内容

一个数组代表河堤的高度，堤坝是等长、等宽的，现在需要在不超过最大预算的前提下，尽可能的加固河堤使最低高度，所有加固的土只能通过一定的成本来运输和填充。一辆车一次只能运输一定量的土，运输成本每次固定，一车土可以填入多个堤坝，填埋每个单位成本固定。求出在不超过给定预算成本的情况下，填埋后的所有河堤岸最低高度的最大值是多少。

输入描述

最大预算成本MaxCosts，(1≤MaxCosts≤1000 0000 0000)\left(1 \le MaxCosts \le 1000\,0000\,0000\right)(1≤MaxCosts≤100000000000)
每车最大载量MaxCapacity，(1≤MaxCapacity≤100)\left(1 \le MaxCapacity \le 100\right)(1≤MaxCapacity≤100)
每车单次运输成本TransportationCostPerShipment，
(1≤TransportationCostPerShipment≤100)\left(1 \le TransportationCostPerShipment \le 100\right)(1≤TransportationCostPerShipment≤100)
每个单位高度的土填埋成本UnitCost，(1≤UnitCost≤100)\left(1 \le UnitCost \le 100\right)(1≤UnitCost≤100)
河堤个数num，(1≤num≤100000)\left(1 \le num \le 100000\right)(1≤num≤100000)
河堤高度数据heights[]，空格分割，数据个数为num。
(0≤heights[i]≤1000000)\left(0 \le heights[i] \le 1000000\right)(0≤heights[i]≤1000000)

输出描述

预算成本内，可以加固的最低高度最大值。
注意，可提高预算情况下，最大值会超过加固前河堤最大高度。

样例1

输入：

100 10 5 2 5 1 2 5 3 4

输出：

11

解释：
最大预算成本100，每车最大载量10，单次运输成本为5，每个单位高度的土填埋成本是2，河堤线长度是5。
最优方案是成本内，所有河堤最低高度加固到11，总共土填埋成本为(11−1+11−2+11−5+11−3+11−4)∗2=80(11-1 + 11-2 + 11-5 + 11-3 + 11-4) * 2=80(11−1+11−2+11−5+11−3+11−4)∗2=80，运输成本是，需要4辆车拉取40个单位的土，运输成本为20，共计花费100，不超过最大预算成本。
如果所有河堤最低高度加固到12，总共土填埋成本为(12−1+12−2+12−5+12−3+12−4)∗2=90(12-1 + 12-2 + 12-5 + 12-3 + 12-4) * 2=90(12−1+12−2+12−5+12−3+12−4)∗2=90。运输成本是，需要5辆车拉取45个单位的土，运输成本为25，共计花费115，超过最大预算成本。

样例2

输入：

50 10 10 1 10 1 2 5 3 4 5 4 1 1 1

输出：

4

解释：
最大预算成本50，每车最大载量10，单次运输成本为10，每个单位高度的土填埋成本是1，河堤线长度是10。
最优方案是成本内，所有河堤最低高度加固到4，总共土填埋成本为(4−1+4−2+4−3+4−1+4−1+4−1)∗1=15(4-1 + 4-2 + 4-3 + 4-1 + 4-1 + 4-1) * 1=15(4−1+4−2+4−3+4−1+4−1+4−1)∗1=15，运输成本是，需要2辆车拉取15个单位的土，运输成本为20，共计花费35，不超过最大预算成本。
如果所有河堤最低高度加固到5，总共土填埋成本为(5−1+5−2+5−3+5−4+5−4+5−1+5−1+5−1)∗1=23(5-1 + 5-2 + 5-3 + 5-4 + 5-4 + 5-1 + 5-1 + 5-1) * 1=23(5−1+5−2+5−3+5−4+5−4+5−1+5−1+5−1)∗1=23，运输成本是，需要3辆车拉取23个单位的土，运输成本为30，共计花费53，超过最大预算成本。

题解和思路

思路

实现思路：二分

1. 标准二分题型，开始确定左右边界left = 0, right = 1e9（足够大）
2. 枚举中间值mdi = (l + r + 1) /2作为河堤岸最低高度，判断是否能在不超过最大成本前提下完成，
   • 能完成更新l = mid
   • 不能完成更新r = mid - 1
3. check逻辑统计需要填充高度数量，并判断 `填充成本 + 运输成本 <= 最大预算成本
4. 算法总体时间复杂度为O(nlogn)

C++

#include<bits/stdc++.h>usingnamespacestd;intmaxCosts,maxCapacity,T,U,n;vector<int>heights;boolcheck(intmid){// 填充土的数量longres=0;for(auto&height:heights){if(height<mid){res+=mid-height;}}// 成本 单位填充 + 运输成本returnres*U+(res+maxCapacity-1)/maxCapacity*T<=maxCosts;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);cin>>maxCosts;cin>>maxCapacity;cin>>T;cin>>U;cin>>n;heights.resize(n);for(inti=0;i<n;i++){cin>>heights[i];}intl=0,r=1e9;// 二分while(l<r){intmid=(l+r+1)>>1;if(check(mid)){l=mid;}else{r=mid-1;}}cout<<l;return0;}

Java

importjava.util.*;publicclassMain{staticlongmaxCosts,maxCapacity,T,U;staticintn;staticint[]heights;staticbooleancheck(longmid){// 填充土的数量longres=0;for(intheight:heights){if(height<mid){res+=mid-height;}}// 成本 = 单位填充成本 + 运输成本returnres*U+((res+maxCapacity-1)/maxCapacity)*T<=maxCosts;}publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);maxCosts=sc.nextLong();maxCapacity=sc.nextLong();T=sc.nextLong();U=sc.nextLong();n=sc.nextInt();heights=newint[n];for(inti=0;i<n;i++){heights[i]=sc.nextInt();}longl=0,r=1000000000L;// 二分while(l<r){longmid=(l+r+1)>>1;if(check(mid)){l=mid;}else{r=mid-1;}}System.out.print(l);}}

python

maxCosts=int(input())maxCapacity=int(input())T=int(input())U=int(input())n=int(input())heights=list(map(int,input().split()))defcheck(mid):# 填充土的数量res=0forheightinheights:ifheight<mid:res+=mid-height# 成本 = 单位填充成本 + 运输成本returnres*U+((res+maxCapacity-1)//maxCapacity)*T<=maxCosts l,r=0,10**9# 二分whilel<r:mid=(l+r+1)//2ifcheck(mid):l=midelse:r=mid-1print(l)

Javascript

constreadline=require("readline");constrl=readline.createInterface({input:process.stdin,output:process.stdout});constinput=[];rl.on("line",(line)=>{input.push(line);});rl.on("close",()=>{letidx=0;constmaxCosts=BigInt(input[idx++]);constmaxCapacity=BigInt(input[idx++]);constT=BigInt(input[idx++]);constU=BigInt(input[idx++]);constn=Number(input[idx++]);constheights=input[idx++].split(" ").map(Number);functioncheck(mid){// 填充土的数量letres=0n;for(constheightofheights){if(BigInt(height)<mid){res+=mid-BigInt(height);}}// 成本 = 单位填充成本 + 运输成本returnres*U+((res+maxCapacity-1n)/maxCapacity)*T<=maxCosts;}letl=0n;letr=1000000000n;// 二分while(l<r){constmid=(l+r+1n)>>1n;if(check(mid)){l=mid;}else{r=mid-1n;}}console.log(l.toString());});

Go

packagemainimport("bufio""fmt""os")var(maxCostsint64maxCapacityint64Tint64Uint64nintheights[]int64)funccheck(midint64)bool{// 填充土的数量varresint64=0for_,height:=rangeheights{ifheight<mid{res+=mid-height}}// 成本 = 单位填充成本 + 运输成本returnres*U+(res+maxCapacity-1)/maxCapacity*T<=maxCosts}funcmain(){in:=bufio.NewReader(os.Stdin)fmt.Fscan(in,&maxCosts)fmt.Fscan(in,&maxCapacity)fmt.Fscan(in,&T)fmt.Fscan(in,&U)fmt.Fscan(in,&n)heights=make([]int64,n)fori:=0;i<n;i++{fmt.Fscan(in,&heights[i])}varlint64=0varrint64=1000000000// 二分forl<r{mid:=(l+r+1)>>1ifcheck(mid){l=mid}else{r=mid-1}}fmt.Print(l)}