T1

题目描述

汪仔最近在玩一款游戏，正值暑假游戏出了夏日活动，可以通过打副本来获得汪仔很喜欢的奖品。游戏的副本里会掉落三种不同的道具（分别是A道具，B道具，C道具），在活动结束后可以使用三种不同的道具各一个来换取一件奖品。虽然这三种道具在游戏中掉落的概率是相同的，但是可能会出现有一些玩家因为运气不佳某一类道具掉落的极少导致最后能获得的奖品数量也很少。良心的游戏策划为了减少这种悲剧的发生，规定可以用任意两个道具（这两个道具可以是同一种也可以不是一种）来交换一个任意指定的道具（比如可以用两个A道具换一个C道具，或者用一个B道具和一个C道具换一个A道具）。现在汪仔有A道具a个，B道具b个，C道具c个。汪仔想知道他最多能交换多少个奖品，你能告诉汪仔吗？

示例1

样例输入

4 4 2

样例输出

3

说明

可以拿一个A道具和一个B道具换一个C道具，这样最后每种道具都有3个，最后可以换3个奖品

示例2

样例输入

9 3 3

样例输出

4

说明

可以拿两个A道具换一个B道具，再拿两个A道具换一个C道具，这样最后有5个A道具4个B道具4个
C道具，最后可以换4个奖品

备注

$1 \leq a, b, c \leq 10 ^ 9$

算法

(二分) $O(log(n))$

1. 设答案为$mid$，超出$mid$的部分之和为$y$，不足$mid$的部分之和为$z$，$y \geq z * 2$说明$mid$可行
2. 上界为最大值，下界为最小值，求$mid$时有可能爆$int$

C++ 代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回能交换奖品的最大数量
     * @param a int整型 
     * @param b int整型 
     * @param c int整型 
     * @return int整型
     */
    typedef long long LL;

    int numberofprize(int a, int b, int c) {
        // write code here
        LL l = min(a, min(b, c)), r = max(a, max(b, c));
        while (l < r) {
            LL mid = l + r + 1 >> 1;
            if (check(mid, a, b, c)) l = mid;
            else r = mid - 1;
        }
        return l;
    }

    bool check(int mid, int a, int b, int c) {
        LL y = max(a - mid, 0) + max(b - mid, 0) + max(c - mid, 0);
        LL z = max(mid - a, 0) + max(mid - b, 0) + max(mid - c, 0);
        return y >= 2 * z;
    }
};

T2

题目描述

某市政府规划建设一个新的小镇，要求小镇上的所有房屋都坐落在同一条东西向大街北侧并且临街
（两座房子不能重叠）。到目前为止，这条街上已经建造了$n$座房子，每座房子的位置是$x_i$，面宽是$a_i$。建造工程师小汪受命在该小镇建造一座新房屋，客户希望他的新房屋面宽为$t$，并且至少贴着之前已有的一座房子建造。您能帮小汪算出这座房屋一共有多少种建法吗？注意：$x_i$为每座房子的中心坐标。

示例1

样例输入

2, [-1, 4, 5, 2]

样例输出

4

说明

要创建一个房屋面宽为2的房屋，其中已有两个房屋A，B，其中A坐标为-1宽度为4，B坐标5宽度为2，这样A占据了-3~1，B占据4~6。因此我们能紧挨这A的东面或西面、或者B的东面或西面建造新房子，一共4种建法。

备注

输入数据是有序的，保证$x_i < x_{i + 1}$

算法

(枚举) $O(n)$

1. 考虑没有房子的情况，返回0，其实官方给的测试中没有这个case，加不加都能AC
2. 考虑精度问题，比较时需要放大2倍，否则只能过40%

C++ 代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回能创建的房屋数
     * @param t int整型 要建的房屋面宽
     * @param xa int整型一维数组 已有房屋的值，其中 x0 a0 x1 a1 x2 a2 ... xi ai 就是所有房屋的坐标和房屋面宽。 其中坐标是有序的（由小到大）
     * @param xaLen int xa数组长度
     * @return int整型
     */
    int getHouses(int t, int* xa, int xaLen) {
        // write code here
        if (!xaLen) return 0;
        int ret = 2;
        for (int i = 0; i + 3 < xaLen; i += 2) {
            int left = 2 * xa[i] + xa[i + 1];
            int right = 2 * xa[i + 2] - xa[i + 3];
            if (right - left > 2 * t) ret += 2;
            else if (right - left == 2 * t) ret ++ ;
        }
        return ret;
    }
};

T3

题目描述

已知长度大于1的浮点数组$arr$(未排序)，求一个切分点$bestidx$，使得切分点左右两个子数组的方差之和最小。（左右两个子序列长度均不为0）。例如数组：$arr = [1,1,1,3,3,3]$，那么最佳切分点$bestidx = 3$，使得$subarr1 = [1,1,1], subarr2 = [3,3,3]$

示例1

样例输入

[1, 1, 1, 3, 3, 3]

样例输出

3

备注

函数参数$arr$作为输入，长度最大不超过100000, 函数应返回$bestidx$作为输出

算法

(前缀和，方差公式) $O(n)$

1. $D(x) = E(x^2) - [E(x)] ^ 2$
2. 分别预处理出原数组的前缀和$s1$以及平方后的数组的前缀和$s2$
3. 枚举分裂点即可

时间复杂度

预处理和枚举过程的时间复杂度均为$O(n)$

C++ 代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param arr float浮点型一维数组 
     * @param arrLen int arr数组长度
     * @return int整型
     */
    int find_best_cut(float* arr, int arrLen) {
        // write code here
        vector<double> s1(arrLen + 1), s2(arrLen + 1);
        for (int i = 1; i <= arrLen; i ++ ) {
            s1[i] = s1[i - 1] + arr[i - 1];
            s2[i] = s2[i - 1] + arr[i - 1] * arr[i  - 1];
        }
        double sigma_sum = INT_MAX;
        int ret = -1;
        for (int i = 2; i <= arrLen; i ++ ) {
            double sigma_left = s2[i - 1] / (i - 1) - (s1[i - 1] / (i - 1)) * (s1[i - 1] / (i - 1));
            double sigma_right = (s2[arrLen] - s2[i - 1]) / (arrLen - i + 1) - ((s1[arrLen] - s1[i - 1]) / (arrLen - i + 1)) * ((s1[arrLen] - s1[i - 1]) / (arrLen - i + 1));
            if (sigma_left + sigma_right < sigma_sum) {
                sigma_sum = sigma_left + sigma_right;
                ret = i;
            }
        }
        return ret - 1;
    }
};