Leetcode刷题100天—倒水（ 百度算法）—day80

前言：

作者：神的孩子在歌唱

大家好，我叫智

倒水 (easy)

Description

桌上有nn个杯子, 第ii个杯子中盛有体积为a_ia**i的水, 该杯子的最大容量为b_ib**i (a_i\le b_ia**i≤b**i)

你可以将一个杯子中的任意体积水倒入另一个杯子(在不超过杯子的最大容量情况下), 也就是说: 水可以在杯子之间任意转移(不考虑水的损耗)

我们希望通过以上方法, 将桌上nn个杯子中的所有水, 置于数量尽可能少的杯子中, 你能解决这个问题吗?

Input

第一行包含1个正整数n(1\le n\le 100)n(1≤n≤100), 含义如题面所述

第二行包含nn个非负整数a_i(0\le a_i\le 100)a**i(0≤a**i≤100), 含义如题面所述

第三行包含nn个非负整数b_i(a_i\le b_i\le 100)b**i(a**i≤b**i≤100), 含义如题面所述

Output

输出一个正整数, 代表所需的杯子的最小数量

Sample Input 1

4
2 3 3 2
7 5 6 7

Sample Output 1

2

Sample Input 2

3                                                                                                                1 2 3                                                                                                            4 5 6

Sample Output 2

1

Hint

对于第一个样例, 可以保留任意两个杯子, 均可以存放2 + 3 + 3 + 2 = 102+3+3+2=10体积的水

对于第二个样例, 只需要保留第三个杯子, 便可以存放1 + 2 + 3 = 61+2+3=6

package 百度算法;

import java.util.Arrays;
import java.util.Scanner;

public class 倒水easy {
    public static void main(String[] args) {

        Scanner st=new Scanner(System.in);
//		非负整数的数量和行数
        int j=st.nextInt();
//		元素

        int[] n=new int[j];
        int[] n1=new int[j];
//		输入元素
        for(int i=0;i<j;i++) {
            n[i]=st.nextInt();

        }
        for(int i=0;i<j;i++) {
            n1[i]=st.nextInt();

        }
        int cut=0;
        int sum=0;
        for (int num:n){
            sum+=num;
        }
        Arrays.sort(n1);
        for (int i=j-1;i>=0;i--){
            if (sum>0){
                cut++;
            }
            sum-=n1[i];
        }
        System.out.println(cut);
    }
}

本人csdn博客：https://blog.csdn.net/weixin_46654114

转载说明：跟我说明，务必注明来源，附带本人博客连接。