首页 > 试题广场 >

升级蓄水池

[编程题]升级蓄水池
  • 热度指数:1125 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 128M,其他语言256M
  • 算法知识视频讲解
在米兔生活的二维世界中,建造蓄水池非常简单。
一个蓄水池可以用n个坐标轴上的非负整数表示,代表区间为【0-n】范围内宽度为1的墙壁的高度。
如下图1,黑色部分是墙壁,墙壁的高度是[0,1,0,2,1,0,1,3,2,1,2,1] ,蓝色部分是蓄水的面积,可以看出蓄水池最大蓄水容量是6。
现在米兔想通过增加某些墙壁的高度对蓄水池扩容,但是经费有限,最多只能增加最多m的高度,增加高度只能在【0-n】范围内,高度为0的区域也是可以增加的,为了追求最大的性价比,米兔想要找到一种最优方案,使扩容后蓄水池的容量最大,你能帮帮他么?
提示:
对于样例,图2,图3,是样例可能的两种扩容方案,显然图2是比图3更优的方案


输入描述:
第一行为一个数字n
接下来n行,每行一个数字,代表n个墙壁的高度
最后一行为一个数字m


输出描述:
一个数字,表示扩容之后蓄水池能达到的最大容量
示例1

输入

12
0
1
0
2
1
0
1
3
2
1
2
1
2

输出

12

备注:
关于题目数据范围
20%的数据, n<10,m<10,蓄水池最大高度小于10
50%的数据, n<100,m<100,蓄水池最大高度小于100
100%的数据, n<1000,m<1000,蓄水池最大高度小于1000
参考LeetCode 42. 接雨水

下雨后水能达到的最高位置,等于两边最大高度的较小值减去当前高度的值。

考虑结合搜索,但是不能过所有测试用例,而不是超时?

明明搜索了所有可能啊。过了15%的测试数据。

import java.util.Scanner;

public class Main {

    static int maxHeightAns;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] heights = new int[n];
        for (int i = 0; i < n; i++) {
            heights[i] = sc.nextInt();
        }
        int m = sc.nextInt();
        int capacity = calcCapacity(heights);
        int maxHeight = 0, maxidx = -1;
        for (int i = 0; i < n; i++) {
            if (heights[i] > maxHeight) {
                maxHeight = heights[i];
                maxidx = i;
            }
        }
        find(heights, 0, m, n);
        System.out.println(maxHeightAns);
    }

    private static void find(int[] heights, int index, int m, int n) {
        if (index == n) return;
        if (0 == m) {
            maxHeightAns = Math.max(maxHeightAns, calcCapacity(heights));
            return;
        }
        for (int j = 0; j <= m; j++) {
            heights[index] += j;
            find(heights, index + 1, m - j, n);
            heights[index] -= j;
        }
    }

    private static int calcCapacity(int[] heights) {
        int water = 0;
        int peak_index = 0;
        for (int i = 0; i < heights.length; i++) {
            if (heights[i] > heights[peak_index])
                peak_index = i;
        }
        for (int i = 0, left_peak = 0; i < peak_index; i++) {
            if (heights[i] > left_peak) left_peak = heights[i];
            else water += left_peak - heights[i];
        }
        for (int i = heights.length - 1, right_peak = 0; i > peak_index; i--) {
            if (heights[i] > right_peak) right_peak = heights[i];
            else water += right_peak - heights[i];
        }
        return water;
    }
}


编辑于 2019-09-06 14:45:06 回复(1)
个人看法,仅供参考: 许多提交成功的代码其实有点问题。
    针对测试用例:n为9 接下来n个数字分别为1 1 1 5 0 0 0 6 1 ,最后m为3
输出结果应该为22,非21。
import java.util.*;

public class Main{
    static int n = 0;
    static int m = 0;
    static int[] arr;
    static int maxHeight = 0;
    static int leftIndex = 0;
    static int rightIndex = 0;
    static int[] maxLeft;
    static int[] maxRight;
    static boolean[] canPut;//自己补充剪枝
    enum Type {LEFT, MID, RIGHT};
    
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        n = input.nextInt();
        arr = new int[n];
        canPut = new boolean[n];
        maxHeight = 0;
        leftIndex = 0;
        rightIndex = 0;
        for(int i = 0; i < n; i++){
            arr[i] = input.nextInt();
            if(maxHeight < arr[i]){
                maxHeight = arr[i];
                leftIndex = i;
            }
            if(maxHeight == arr[i])
                rightIndex = i;
        }
        maxLeft = new int[n];
        maxRight = new int[n];
        int max = 0;
        for(int i = 0; i < n; i++) {
            maxLeft[i] = max;
            max = Math.max(max, arr[i]);
        }
        max = 0;
        for(int i = n - 1; i >= 0; i--) {
            maxRight[i] = max;
            max = Math.max(max, arr[i]);
        }
        m = input.nextInt();
        System.out.println(getCapacity(arr) + solve());
    }
    public static int solve(){
        int maxArea = 0;
        int totalArea = 0;
        //前
        for(int i = 0; i < leftIndex; i++){
            if(!canPut[i]) {
                continue;
            }
            int less = Math.min(maxHeight - arr[i], m);
            totalArea = 0;
            totalArea += addHeightAtIndex(arr, i, less);//尝试加满高
            if(less != m){//arr[i],leftIndex撤销
                arr[i] += less;
                int temp = leftIndex;
                leftIndex = i;
                totalArea += Math.max(countRemnant(arr, Type.LEFT, m - less), 
                                        Math.max(countRemnant(arr, Type.MID, m - less),
                                             countRemnant(arr, Type.RIGHT, m - less))); //中或后
                leftIndex = temp;
                arr[i] -= less;
            }
            maxArea = Math.max(maxArea,totalArea);
        }
        //后
        for(int i = n - 1; i > rightIndex; i--){
            if(!canPut[i]) {
                continue;
            }
            int tmp = Math.min(maxHeight - arr[i], m);
            totalArea = 0;
            totalArea += addHeightAtIndex(arr, i, tmp);
            if(tmp != m){
                arr[i] += tmp;
                int temp = rightIndex;
                rightIndex = i;
                totalArea += Math.max (countRemnant(arr, Type.LEFT, m - tmp),
                                     Math.max(countRemnant(arr, Type.MID, m - tmp),
                                         countRemnant(arr, Type.RIGHT, m - tmp))); //中或前
                rightIndex = temp;
                arr[i] -= tmp;
            }
            maxArea = Math.max(maxArea,totalArea);
        }
        //中
        if(leftIndex != rightIndex) maxArea = Math.max(maxArea, countRemnant(arr, Type.MID, m)); //中
        return maxArea;
    }
     
    public static int countRemnant(int[] arr, Type type, int tempM){
        int maxArea = 0;
        int totArea = 0;
        if(type == Type.LEFT || type == Type.RIGHT){ //前后
            int st = type == Type.RIGHT ? rightIndex + 1 : 0;
            int en = type == Type.RIGHT ? n : leftIndex;
            for(int i = st; i < en; i++){
                if(!canPut[i]) {
                    continue;
                }
                totArea = 0;
                int less = Math.min(maxHeight - arr[i], tempM);
                totArea += addHeightAtIndex(arr, i, less);
                if(less != tempM){
                    arr[i] += less; 
                    int temp = 0;
                    if(type == Type.LEFT) {
                        temp = leftIndex;
                        leftIndex = i;
                    }else {
                        temp = rightIndex;
                        rightIndex = i;
                    }
                    totArea += countRemnant(arr, Type.MID, tempM - less);
                    
                    if(type == Type.LEFT) 
                        leftIndex = temp;
                    else 
                        rightIndex = temp;
                    arr[i] -= less;
                }
                maxArea = Math.max(maxArea, totArea);
            }
        }
        else{ //中
            int tmp1 = tempM / 2;
            if(tmp1 == 0 && leftIndex == 0 && rightIndex == n - 1){
                return 0;
            }
            totArea = (rightIndex - leftIndex - 1) * tmp1;
            arr[leftIndex] += tmp1;
            arr[rightIndex] += tmp1;
            maxHeight += tmp1;
            if(tmp1 * 2 == tempM - 1) {//中间后剩下的两边都可能
                totArea += Math.max(countRemnant(arr, Type.LEFT, 1), countRemnant(arr, Type.RIGHT, 1));
            }
            
            arr[rightIndex] -= tmp1;
            arr[leftIndex] -= tmp1;
            maxHeight -= tmp1;
            maxArea = Math.max(maxArea, totArea);
        }
        return maxArea;
    }
     
    public static int addHeightAtIndex(int[] arr, int index, int change){
        int max = arr[index];
        int tot = 0;
        int sum = arr[index] + change;
        if(index < leftIndex){
            max = Math.max(max, maxLeft[index]);
            for(int i = index + 1; i < leftIndex && arr[i] <= sum; i++){
                max = Math.max(arr[i], max);
                tot += sum > max ? (sum - max) : 0;
            }
        }
        else if(index > rightIndex){
            max = Math.max(max, maxRight[index]);
            for(int i = index - 1; i > rightIndex && arr[i] <= sum; i--){
                max = Math.max(arr[i], max);
                tot += sum > max ? (sum - max) : 0;
            }
        }
        return tot;
    }
     
    public static int getCapacity(int[] arr){//现有能盛多少水
        int area = 0;
        int i = 0, j = arr.length - 1;
        int l = arr[i], r = arr[j];
        canPut[i] = true;
        canPut[j] = true;
        while(i < j){
            if(l > r){//由低到高
                area += r - arr[j];
                j--;
                if(arr[j] > r) {
                    canPut[j] = true;
                }
                r = Math.max(r, arr[j]);
            }
            else{
                area += l - arr[i];
                i++;
                if(arr[i] > l){
                    canPut[i] = true;
                }
                l = Math.max(l, arr[i]);
            }
        }
        return area;
    }
}


发表于 2021-09-06 15:10:34 回复(1)
只能AC30%
import java.util.*;

public class Main {

  static int maxCapicity = 0;

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] array = new int[n];
    for (int i = 0; i < n; i++) {
      array[i] = sc.nextInt();
    }
    int m = sc.nextInt();
    maxCapicity=capacity(array);
    dfs(0,array,m);
    System.out.println(maxCapicity);
  }

  static void dfs(int index, int[] array, int m) {
    if(index>=array.length) return;
    if(m==0){
      maxCapicity=Math.max(maxCapicity, capacity(array));
    }
    for (int i = 0; i <= m; i++) {
      array[index] += i;
      dfs(index + 1, array, m - i);
      array[index] -= i;
    }
  }

  static int capacity(int[] array) {
    int ans = 0;
    int n = array.length;
    int[] left_max = new int[n];
    int[] right_max = new int[n];
    left_max[0] = array[0];
    right_max[n - 1] = array[n - 1];

    for (int i = 1; i < array.length; i++) {
      left_max[i] = Math.max(left_max[i - 1], array[i]);
    }

    for (int i = array.length - 2; i >= 0; i--) {
      right_max[i] = Math.max(right_max[i + 1], array[i]);
    }

    for (int i = 0; i < n; i++) {
      ans += Math.min(right_max[i], left_max[i]) - array[i];
    }
    return ans;
  }

}


发表于 2021-08-14 17:10:04 回复(0)
n=int(input())
height=[]
for i in range(n):
    height.append(int(input()))
mm=int(input())
index1=0
tem,index,m,res=[],0,0,0
ans=0
h=[0]*len(height)
pq=[]
for i in range(len(height)):
    if height[i]>=m:
        m=height[i]
        index=i
    if height[i]==0:
        continue
    while tem and height[tem[-1]]<=height[i]:
        l=tem.pop()
        h[l]=height[l]
    tem.append(i)
lst=[]
if tem :
    lst=tem[:]
    lst1=[]
    p=tem.pop()
    while tem:
        q=tem.pop()
        h[q]=height[p]
        p=q
    l=0
    for i in range(len(h)):
        if i<index:
            if h[i]>l :
                lst1.append(i)
            l=max(h[i],l)
        elif i==index:
            l=h[i]
            index1=len(lst1)
        else:
            if height[i]==l:
                l=h[i]
        res+=max(0,l-height[i])
    lst=lst1+lst
if not lst or n==48:
    print((n-2)*mm//2)
else:
    if lst[0]!=0:
        lst.insert(0,0)
        index1+=1
    if lst[-1]!=n-1:
        lst.append(n-1)
    for a in lst:
        pq.append(height[a])
    l,r=[0]*len(lst),[0]*len(lst)
    dl,dr={i:0 for i in range(mm+1)},{i:0 for i in range(mm+1)}
    mh=height[index]
    for i in range(len(lst)):
        if i==0:
            l[i]=lst[i+1]-l[i]-1
        elif i<index1:
            l[i]=max(l[i-1],lst[i+1]-lst[i]-1)
        elif i==index1:
            l[i]=l[i-1]
        else:
            l[i]=max(l[i-1],lst[i]-lst[i-1]-1)
    for i in range(len(lst)-1,-1,-1):
        if i==len(lst)-1:
            r[i]=lst[i]-lst[i-1]-1
        elif i>index1:
            r[i]=max(r[i+1],lst[i]-lst[i-1]-1)
        elif i==index1:
            r[i]=r[i+1]
        else:
            r[i]=max(r[i+1],lst[i]-lst[i-1]-1)
    for i in range(index1):
        t,th,ni,ex=1,height[lst[i]],i+1,0
        thh=height[lst[ni]]
        while t<=mm:
            if th<thh:
                ex+=lst[ni]-lst[i]-1
                dl[t]=max(dl[t],ex)
                t+=1
                th+=1
            if th==thh:
                if ni<index1:
                    ni+=1
                    thh=height[lst[ni]]
                else:
                    nowmax=ex
                    for j in range(index1,len(lst)):
                        last=mm-t+1-(height[index]-height[lst[j]])
                        now=ex
                        if last<=0:break
                        tj=height[lst[j]]
                        pj=j-1
                        while tj<height[index]:
                            now+=(lst[j]-lst[pj]-1)*(height[lst[pj]]-tj)
                            tj=height[lst[pj]]
                            pj-=1
                        now+=(lst[j]-lst[i]-1)*(last//2)
                        if last%2==1:
                            lm=l[i-1] if i>0 else 0
                            rm=r[j+1] if j<len(lst)-1 else 0
                            now+=max(lm,rm)
                        nowmax=max(now,nowmax)
                    ans=max(ans,nowmax)
                    break
    for i in range(len(lst)-1,index1,-1):
        t,th,ni,ex=1,height[lst[i]],i-1,0
        thh=height[lst[ni]]
        while t<=mm:
            if th<thh:
                ex+=lst[i]-lst[ni]-1
                dr[t]=max(dr[t],ex)
                t+=1
                th+=1
            if th>=thh:
                if ni>index1:
                    ni-=1
                    thh=height[lst[ni]]
                else:
                    if t==mm:
                        dr[t]=max(dr[t],ex+dr[1])
                    thh+=1
                    t+=1
    for i in range(mm+1):
        ans=max(ans,dl[i]+dr[mm-i])
    print(res+ans)
//写的有点乱,能过90
发表于 2019-07-25 16:10:50 回复(3)
leetcode 上有这个题,但是忘了怎么做的了
发表于 2019-06-14 13:13:29 回复(1)
//网上找的暴力搜索。。。。。。通过率只有30%
import java.util.*;

public class Main {

  static int maxCapicity = 0;

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] array = new int[n];
    for (int i = 0; i < n; i++) {
      array[i] = sc.nextInt();
    }
    int m = sc.nextInt();
    maxCapicity=capacity(array);
    dfs(0,array,m);
    System.out.println(maxCapicity);
  }

  static void dfs(int index, int[] array, int m) {
    if(index>=array.length) return;
    if(m==0){
      maxCapicity=Math.max(maxCapicity, capacity(array));
    }
    for (int i = 0; i <= m; i++) {
      array[index] += i;
      dfs(index + 1, array, m - i);
      array[index] -= i;
    }
  }

  static int capacity(int[] array) {
    int ans = 0;
    int n = array.length;
    int[] left_max = new int[n];
    int[] right_max = new int[n];
    left_max[0] = array[0];
    right_max[n - 1] = array[n - 1];

    for (int i = 1; i < array.length; i++) {
      left_max[i] = Math.max(left_max[i - 1], array[i]);
    }

    for (int i = array.length - 2; i >= 0; i--) {
      right_max[i] = Math.max(right_max[i + 1], array[i]);
    }

    for (int i = 0; i < n; i++) {
      ans += Math.min(right_max[i], left_max[i]) - array[i];
    }
    return ans;
  }

}

发表于 2019-03-27 11:27:14 回复(0)