腾讯机试题

时间：2019.04.05

1

题：
小 Q 非常喜欢喝橙汁，在他生日的时候他的父母送了他 n 瓶橙汁，第 i 瓶橙汗的体积是 $v_i$ 呈升。小Q想先喝一部分，剩下的后面慢慢喝。他想先倒出 s 毫升给自己喝，同时为了获得双倍的快乐，他想让剩下的橙汁中体积最少的尽可能大。请你帮助他计算出当他倒了 s 毫升果汁并且获得了双倍的快乐后剩下的橙汁中体积最少的是多少
注意从每瓶橙汁中取走的橙汁的体积只能是整数。

输入描述：
第一行两个整数 n，s，用一个空格分隔；
第二行 n个整数$v_i$，表示每瓶果汁的体积，每两个正整数之间用一个空格分隔。
满足$1<=n<=1000,1<=s<=10^9,1<=v_i<=10^9$
输出描述：
一个整数，表示最少的橙汁的体积。如果无法倒出 s 毫升的橙汁，则输出一1。

示例1
输入
3 5
1 1 1
输出
-1

示例2
输入
2 9
5 10
输出
3

case通过率 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

题：
小Q打算穿越怪兽谷。他不会打怪，但是他有钱。他知道，只要给怪兽一定的金币，怪兽就会一 直护送着他出谷。
在谷中，他会依次遇见N只怪兽，每只怪兽都有目己的武力值和要“贿赔”它所需的金币数。如果小 Q 没有“贿赔”某只怪兽，而这只怪兽“武力值”又大于护送他的怪兽武力之和，这只怪兽就会攻击他。
小 Q 想知道，要想成功穿越怪兽谷而不被攻击，他最少要准备多少金币。

输入描述：
第一行输入一个整数N，代表怪兽的只数。
第二行输入N个整数$d_1，d_2，...，d_n$，代表武力值
第三行输入N个整数$p_1，p_2，...，p_n$，代表收买N只怪兽所需的金币数。
输出描述：
输出一个整数，代表所需最小金币数

示例1
输入
3
8 5 10
1 1 2
输出
2

示例2
输入
4
1 2 4 8
1 2 1 2
输出
6

此题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

题：
小 Q 有一天突发奇想，把 1 到$2\ast n$的数分为相同大小的两组 A 和 B(即长度都是n)。
然后按照从小到大排序之后，对于 1 <= i <= n，均满足 abs(A[i] - B[i]) >= k。其中 abs标识求绝对值。
小 Q 觉得这个问题对于他没有挑战，所以想考考你，让你计算出所有满足条件的分配方案数。

输入描述：
输入两个整数 n (1 <= n <= 50)，k (1 <= k <= 10)。
输出描述：
输出一个整数

示例1
输入
2 2
输出
2
说明
A = {1, 2} B = {3, 4}
A = {3, 4} B = {1, 2}

此题没有写完。。但是就差一步。
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() {
    }
}

原题图片

1

2

3