蓄水池并发注水问题-算法题（java/c++）

当前有n个水池（n无大小限制，此处0

输入：
time = [2,4,10]
costs = [2,5,7]
x=7
输出：14

    public static int minTime(int[] time,int[] costs,int x){
        int temp,times=0,tmp_x=x;
        if(time.length==0 || costs.length==0){
            return times;
        }
//        按时间排序
        for(int i=1;i<time.length;i++){
            for(int j=0;j<time.length-i;j++){
                if(time[j]<time[j+1]){
                    temp=time[j];
                    time[j]=time[j+1];
                    time[j+1]=temp;
                    temp=costs[j];
                    costs[j]=costs[j+1];
                    costs[j+1]=temp;
                }
            }
        }
//        复制一个临时数组，用于删除使用过的元素
        int[] tmp_time=(int[]) Arrays.copyOf(time,time.length);
        int[] tmp_costs=(int[]) Arrays.copyOf(costs,costs.length);
        int len=tmp_costs.length;
        
//        开始获取时间
        for(int i=0;i<costs.length;i++){
//            判断人数是否满足条件
            if(tmp_x>=costs[i]){
//                每一次统计只取同时进行所花最大时间
                if(times<time[i]){
                    times=time[i];
                }
                tmp_x-=costs[i];
//                删除使用过的元素
                for(int k=i;k<len-1;k++){
                    tmp_costs[k]=tmp_costs[k+1];
                    tmp_time[k]=tmp_time[k+1];
                }
                tmp_costs[len-1]='\0';
                tmp_time[len-1]='\0';
                len--;
            }
            if(tmp_x==0){ break; }

        }
        return times+minTime((int[]) Arrays.copyOf(tmp_time,len),(int[]) Arrays.copyOf(tmp_costs,len),x);
    }

暴力了一种解法，看看小伙伴能不能再优化优化：

import java.util.*;
import java.util.stream.Collectors;


public class Main {

    public static void main(String[] args) {
        int[] time = {3, 2,4, 10};
        int[] costs = {2, 2,5, 7};
        int x = 7;
        System.out.println(minTime(time,costs,x));

    }

    public static int minTime(int[] time, int[] costs, int x) {
        List<TimeAndCost> list = new ArrayList<>();
        for (int i = 0, len = time.length; i < len; i++) {
            list.add(new TimeAndCost(time[i], costs[i]));
        }
        int cost=0;
        Collections.sort(list);
        while (list.size()>0){//还有池子没填完
            //有为0的池子吗，如果有，释放对应的资源
            for (TimeAndCost timeAndCost : list) {
                if (timeAndCost.running){
                    timeAndCost.time-=1;
                }
                if (timeAndCost.time==0){
                    timeAndCost.over=true;
                    x+=timeAndCost.cost;
                }
            }
            list=list.stream().filter(timeAndCost -> !timeAndCost.over).collect(Collectors.toList());
            //现有资源够分配吗，够分配的话，开始够分配的任务，资源减少，任务时间减少
            for (TimeAndCost timeAndCost : list) {
                if (!timeAndCost.running&&timeAndCost.cost<=x){
                    timeAndCost.running=true;
                    timeAndCost.time-=1;
                    x-=timeAndCost.cost;
                }
            }
            cost++;
        }
        return cost;
    }

    static class TimeAndCost implements Comparable<TimeAndCost> {
        int time;
        int cost;
        boolean over;
        boolean running;
        public TimeAndCost(int time, int cost) {
            this.time = time;
            this.cost = cost;
            over=false;
            running=false;
        }

        @Override
        public int compareTo(TimeAndCost o) {
            if (o.cost > this.cost) {
                return -1;
            }
            if (o.cost < this.cost) {
                return 1;
            }
            return Integer.compare(this.time, o.time);
        }
    }
}

问题解决代码如下，望采纳：

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] time = {2, 4, 10};
        int[] costs = {2, 5, 7};
        int x = 7;

        // 根据costs从小到大排序
        int[] sortedTime = Arrays.copyOf(time, time.length);
        Arrays.sort(costs);
        for (int i = 0; i < time.length; i++) {
            for (int j = 0; j < time.length; j++) {
                if (time[i] == sortedTime[j]) {
                    time[i] = costs[j];
                    break;
                }
            }
        }

        int totalTime = 0;
        int workers = x;

        // 从最短时间的水池开始蓄水，一直到无法蓄水
        for (int i = 0; i < time.length; i++) {
            if (time[i] <= workers) {
                totalTime += time[i];
                workers -= time[i];
            } else {
                break;
            }
        }

        System.out.println(totalTime); // 输出14
    }
}

如有帮助望采纳

public static List<String> extractLines(String filePath, int n) throws IOException {
        List<String> randomLines = new ArrayList<>();
        FileReader fr = new FileReader(filePath);
        BufferedReader br = new BufferedReader(fr);
        for (int j = 0; j < n; j++) {
            String line = br.readLine();
            randomLines.add(line);
        }
        for (int i = 0;; i++) {
            String readLine = br.readLine();
            if (StringUtils.isBlank(readLine)) {
                break;
            }
            Random random = new Random();
            int nextInt = random.nextInt(n + i) ;
            if (nextInt < n) {
                randomLines.remove(nextInt);
                randomLines.add(readLine);
            }
        }
        return randomLines;
    }

public static List<String> extractLines(String filePath, int n) throws IOException {
        List<String> randomLines = new ArrayList<>();
        FileReader fr = new FileReader(filePath);
        BufferedReader br = new BufferedReader(fr);
        for (int j = 0; j < n; j++) {
            String line = br.readLine();
            randomLines.add(line);
        }
        for (int i = 0;; i++) {
            String readLine = br.readLine();
            if (StringUtils.isBlank(readLine)) {
                break;
            }
            Random random = new Random();
            int nextInt = random.nextInt(n + i) ;
            if (nextInt < n) {
                randomLines.remove(nextInt);
                randomLines.add(readLine);
            }
        }
        return randomLines;
    }

这不初中数学题吗