首页 > 阿里笔试7.29 线性复杂度
头像
tuogy
编辑于 2020-07-29 16:42
+ 关注

阿里笔试7.29 线性复杂度


第一题

n 个恐龙蛋及恐龙蛋的大小,按降序排列。第 i 个恐龙蛋每天增大 i,问最少几天会出现两个同样大小的恐龙蛋。

分析:根据题意,相邻的恐龙蛋增长速度相差为1因此,如果相邻蛋的大小差异数组d为{d1, d2, …, dn-1},那么每经过1天,数组d中每个元素都会减少1。
当d中首次出现0元素时,就是首次出现两个相同大小恐龙蛋的时候。这很容易证明,因为根据题设,d中的元素均非负。在d中出现0元素之前,恐龙蛋大小是严格递减的,不存在相同大小的蛋。
很显然,d中首次出现0元素的天数,就是数组d中的最小值。数组d及其最小值可以在O(n)时间内计算得到。算法的时间复杂度为O(n)。

int solve() {
    int n, ret = INT_MAX;
    cin >> n;
    for (int i = 0, prev = INT_MAX, cur = 0; i < n; i++) {
        cin >> cur;
        ret = min(ret, prev - cur);
        prev = cur;
    }
    return ret;
}


第二题

n 个客栈依次排列,给出 n - 1 条路的权重。从任意一处出发,每走过一条路,该路的权重减 1,但得到1 点利益。不能走权重为 0 的路。求最大利益。

分析:题中涉及到一个图An,An的n个顶点是n个客栈。其中第k-1个客栈到第k个客栈的边的权重用v[k-1]表示。我们采用动态规划去求解这个问题。假设Lk是由第0,…,k个客栈所组成的An的子图,Rk是由第k, …,n-1个客栈所组成的An的子图。
定义以下变量:
f_l[k] // 从第k个客栈出发,在L_k中获得的最大利益
f_r[k] // 从第k个客栈出发,在R_k中获得的最大利益
g_l[k] // 从第k个客栈出发,并在第k个客栈结束,在L_k中获得的最大利益
g_r[k] // 从第k个客栈出发,并在第k个客栈结束,在R_k中获得的最大利益 

如果v[k-1]是奇数,那么

f_l[k] = f_l[k-1] + v[k-1]  // 首先在客栈k-1和k中反复横跳耗尽该边的权重
g_l[k] = (v[k-1] > 1) ? (g_l[k-1] + v[k-1] - 1) : 0 
// 因为要回到出发点,v[k-1]只能遍历偶数次 

如果v[k-1]是偶数,那么

g_l[k] = (v[k-1] > 0) ? (g_l[k-1] + v[k-1]) : 0  
//在客栈k-1和k中反复横跳耗尽该边的权重
f_l[k] = max((v[k-1] > 0) ? (f_l[k-1] + v[k-1] - 1) : 0, g_l[k])  
// 要么最终回到客栈k;要么不回到客栈k,但此时v[k-1]只能遍历奇数次 
我们可以令k=0,1,...,n-1,利用DP计算出所有的f_l[k], g_l[k]。初始条件显然有f_l[0] = g_l[0] = 0。
f_r[k]g_r[k]的计算是完全对称的,只不过按照k=n-1,...,1,0逆序计算。时间复杂度为O(n)

在计算出了f_l, f_r, g_l, g_r后,我们考虑计算原问题的解。假设我们从第k个客栈出发,并在第k’个客栈结束。
如果k’≤k,最大收益为f_l[k]+g_r[k]。因为对于客栈k右边的权值,我们必须从第k个客栈出发开始遍历,并最终回到第k个客栈。类似地,如果k’≥k,最大收益为f_r[k]+g_l[k]。
因此,原问题的解为,可以在O(n)的时间内求解。
int solve() {
    int n, ret = 0;
    cin >> n;
    vector<int> v(n - 1), f_l(n, 0), f_r(n, 0), g_l(n, 0), g_r(n, 0);
    for (int i = 0; i < n - 1; i++) cin >> v[i];
    for (int k = 1; k < n; k++) {
        if (v[k - 1] & 1) {
            f_l[k] = f_l[k - 1] + v[k - 1];
            g_l[k] = v[k - 1] > 1 ? g_l[k - 1] + v[k - 1] - 1 : 0;
        }
        else {
            g_l[k] = v[k - 1] ? g_l[k - 1] + v[k - 1] : 0;
            f_l[k] = max(g_l[k], v[k - 1] ? f_l[k - 1] + v[k - 1] - 1 : 0);
        }
    }
    for (int k = n - 2; k >= 0; k--) {
        if (v[k] & 1) {
            f_r[k] = f_r[k + 1] + v[k];
            g_r[k] = v[k] > 1 ? g_r[k + 1] + v[k] - 1 : 0;
        }
        else {
            g_r[k] = v[k] ? g_r[k + 1] + v[k] : 0;
            f_r[k] = max(g_r[k], v[k] ? f_r[k + 1] + v[k] - 1 : 0);
        }
    }
    for (int k = 0; k < n; k++) 
        ret = max(ret, max(f_l[k] + g_r[k], f_r[k] + g_l[k]));
    
    return ret;
}


全部评论

(17) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐