Tencent machine test questions

Time ：2019.04.05

1

topic ：
Small Q I like orange juice very much , His parents gave him a gift on his birthday n A bottle of orange juice , The first i The volume of bottle orange sweat is $v_i$ Ascending . Small Q Want to drink some first , Drink the rest slowly . He wants to pour it out first s Ml for yourself , At the same time, in order to get double happiness , He wants the smallest volume of the remaining orange juice to be as large as possible . Please help him calculate when he falls s What is the smallest volume of orange juice left after ml of juice and double happiness
Note that the volume of orange juice taken from each bottle of orange juice can only be an integer .

Input description ：
The first line has two integers n,s, Separate... With a space ;
The second line n It's an integer $v_i$, Indicates the volume of each bottle of juice , Every two positive integers are separated by a space .
Satisfy $1<=n<=1000,1<=s<=10^9,1<=v_i<=10^9$
Output description ：
An integer , Represents the minimum volume of orange juice . If you can't pour it out s Ml orange juice , Then output one 1.

 Example 1
 Input 
3 5
1 1 1
 Output 
-1

 Example 2
 Input 
2 9
5 10
 Output 
3

case Passing rate  40%
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int s = sc.nextInt();
        int [] v = new int[n];
        int sum = 0;
        int min = 1000000001;
        for(int i = 0; i < n; i++){
            v[i] = sc.nextInt();
            sum += v[i];
            if(min > v[i]) {
                min = v[i];
            }
        }
        if(s > sum) {
            System.out.println(-1);
        } else if((sum - s)/ n < min ) {
            System.out.println((sum - s)/ n);
        } else {
            System.out.println(min);
        }
    }
}

2

topic ：
Small Q Plan to cross the monster Valley . He can't play strange , But he has money . He knows that , Just give the monster a certain amount of gold , Monsters will one Directly escorted him out of the valley .
In the valley , He will meet in turn N A monster , Every monster has its own force value and wants “ Bribe compensation ” The number of gold coins it needs . If small Q No, “ Bribe compensation ” Some monster , And this monster “ Force value ” And more than the sum of the monster forces escorting him , This monster will attack him .
Small Q Want to know , To successfully cross the monster valley without being attacked , How many gold coins should he prepare at least .

Input description ：
Enter an integer in the first line N, The number of monsters .
Second line input N It's an integer $d_1,d_2,...,d_n$, Represents force value
In the third line, enter N It's an integer $p_1,p_2,...,p_n$, On behalf of buying N The number of gold coins needed by a monster .
Output description ：
Output an integer , Represents the minimum number of gold coins required

 Example 1
 Input 
3
8 5 10
1 1 2
 Output 
2

 Example 2
 Input 
4
1 2 4 8
1 2 1 2
 Output 
6

 This question AC
import java.util.Scanner;

public class Main {
    static long [] power;
    static int [] gold;
    static int n;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        power = new long [n];
        gold = new int [n];
        for(int i = 0; i < n; i ++) {
            power[i] = sc.nextLong();
        }
        for(int i = 0; i < n; i ++) {
            gold[i] = sc.nextInt();
        }
        System.out.println(foo(power[0], gold[0], 1));
    }
    static int foo(long self, int sum, int i) {
        if(i == n) {
            return sum;
        }
        if(self < power[i]) {
            return foo(self + power[i], sum + gold[i], i + 1);
        } else {
            int a = foo(self + power[i], sum + gold[i], i + 1);
            int b = foo(self, sum, i + 1);
            return a < b ? a : b;
        }
    }
}

3

topic ：
Small Q One day I had a whim , hold 1 To $2\ast n$ The number of is divided into two groups of the same size A and B( That is, the length is n).
Then sort from small to large , about 1 <= i <= n, All meet abs(A[i] - B[i]) >= k. among abs Identify the absolute value .
Small Q I don't think this problem is a challenge for him , So I want to test you , Let you calculate the number of distribution schemes that meet the conditions .

Input description ：
Enter two integers n (1 <= n <= 50),k (1 <= k <= 10).
Output description ：
Output an integer

 Example 1
 Input 
2 2
 Output 
2
 explain 
A = {1, 2} B = {3, 4}
A = {3, 4} B = {1, 2}

 This question is not finished .. But it's one step away .
import java.util.Scanner;

public class Main {
    static int n;
    static int k;
    static int [] a;
    static int [] b;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = 2 * sc.nextInt());
        k = sc.nextInt();
        a = new int [n / 2];
        b = new int [n / 2];
        System.out.println(sum(0, 0, true) + sum(0, 0, false));
    }
    static int sum(int i, int j, boolean b) {
        if(i + j + 2 == n) {
            return judge()?0:1;
        }
        if(b) {
            a[i] = i + j;
            return sum(i + 1, j, true) + sum(i + 1, j, false);
        } else {
            b[j] = i + j;
            return sum(i, j + 1, true) + sum(i, j + 1, false);
        }
    }
    static boolean judge() {
    }
}

Original picture

1

2

3