腾讯(1)

1. 小Q的减法
   描述：给定一个数组，每次输出其非0的最小值，之后数组减去该最小值，不断循环，直到达到迭代次数或者所有数字都为0(此时输出为0)
   代码实现：

package com.bj.test;
import java.util.Scanner;
/**
 * 测试用例：
 * 2 2
   4 6
   4
   2
   -----------
   2 1
   5 1
   1
 *
 */
public class Array_Sub {
    public static void main(String[] args) {
        // 1.读取数据
        Scanner in = new Scanner(System.in);
        int num_count = 0;
        int times = 0;
        if(in.hasNextLine()){
            String str1[] = in.nextLine().split(" ");
            num_count = Integer.parseInt(str1[0]);
            times = Integer.parseInt(str1[1]);
        }
        int nums [] = new int[num_count];
        if(in.hasNextLine()) {
            String str2[] = in.nextLine().split(" ");
            for (int i = 0; i < nums.length; i++) {
                nums[i] = Integer.parseInt(str2[i]);
            }
        }
        in.close();
        int index = 0;
        while (index<times) {
            //如果所有为0，输出0
            if(zero_array(nums)){
                System.out.println(0);
                break;
            }
            //输出当前最小值(非0)
            int temp = min_array(nums);
            System.out.println(temp);
            //数组减去最小值
            array_sub(nums,temp);
            index++;
        }
    }
    // 判断数组是否全0
    public static boolean zero_array(int num[]){
        for (int i = 0; i < num.length; i++) {
            if(num[i]!=0)return false;
        }
        return true;
    }
    // 当前数组中除0之外的最小值
    public static int min_array(int num[]){
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < num.length; i++) {
            if (num[i]<min && num[i]!=0) {
                min = num[i];
            }
        }
        return min;
    }
    // 数组中每个值减去一个值
    public static void array_sub(int num[],int min){
        for (int i = 0; i < num.length; i++) {
            num[i] -= min;
        }
    }

}

2. 水果交易
   数组:{5,-4,1,-3,1}分别表示每个村庄的买入水果数和卖出水果数，>0 表示买入，卖出的水果搬到相邻村庄代价为1,所有卖出和买入的和为0,求完成水果交易最小的移动代价？
   即：-3移到相邻的两个1，代价为2，剩余一个-1移到5代价为3，-4移到5，代价为4，总代价为2+3+4=9
   代码实现：

package com.bj.test;
import java.util.Scanner;
/**
 * 测试用例
    5
    5,-4,1,-3,1
    9
    其中，5表示5个村庄
 *
 */
public class Fruits_Deal {
    public static void main(String[] args) {
        // 1.输入
        Scanner in = new Scanner(System.in);
        int num = 0;
        if (in.hasNextLine()) {
            num = Integer.parseInt(in.nextLine());
        }
        int nums [] = new int[num];
        if(in.hasNextLine()) {
            String temp[] = in.nextLine().split(",");
            for (int i = 0; i < temp.length; i++) {
                nums[i] = Integer.parseInt(temp[i]);
            }
        }
        in.close();
        //2.求最小代价
        int curr_data = nums[0];
        int curr_time = 0;
        for (int i = 1; i < nums.length; i++) {
            curr_time += Math.abs(curr_data);  // 当前次数
            curr_data = curr_data+nums[i]; // 当前值
        }
        System.out.println(curr_time);
    }

}

3. 数的拆分
   描述:一个数字有两种拆法：
   ① 数字减1
   ② 所有数字都拆分成两个更小的数之和；
   求将数字拆分变为0，需要多少轮？

输入取值范围： 1<= N <=100, 0<=K<=100
样例： 输入 5 2 ，输出 4。 输入15 4，输出 6

定义数组dp[i][j]为将数字i拆分j次转为0需要的次数，dp[i][j] = min(dp[i-1][j-1], dp[(i+1)/2][j-1]) + 1 , dp[i-1][j] 代表这次不拆分，减去1， dp[(i+1)/2][j-1] 代表这次进行拆分，拆分成两个中位数(拆分为两个中位数保证其拆分次数更小)
代码实现

package com.bj.test;
import java.util.Scanner;
/**
测试用例：
5 2
4
---
15 4
6
 */
public class Number_Split {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str [] = in.nextLine().split(" ");
        in.close();
        int num = Integer.parseInt(str[0]);
        int times = Integer.parseInt(str[1]);
        if (num<=0) {
            return;
        }
        // 动态规划数组
        int [][] db = new int[101][101];
        // 初始化行
        for (int i = 0; i < db.length; i++) {
            db[i][0] = i;
        }
        // 初始化列(表示数字1拆分或者减去多少次都是1)
        for (int i = 0; i < db[0].length; i++) {
            db[1][i] = 1;
        }
        for (int i = 2; i <=num; i++) {
            for (int j = 1; j <= times; j++) {
                db[i][j] = Math.min(db[i-1][j], db[(i+1)/2][j-1])+1;
            }
        }
        System.out.println(db[num][times]);
    }
}