2020.4.3 阿里巴巴 笔试题
第一题:
小强和小明是很好的朋友,有一天小强在刷题的时候遇到一一个他从来没遇到过的问题,问题是这样描述的:
给你一个长度n数组a,问数组中有多少有价值的数?规定若ax为有价值的数,当且仅当:
x左侧存在大于ax的数,右侧存在小于ax的数,论左侧最小的大于ax的数为f,右侧小于ax的最大的数记为g: f为g的倍数。
输入描述:
输入包含两行,第1行仅一个整数n,表示数组的长度接下来一行有n个整数,表示数组a
保证全部数据: 1≤n≤10^5,1≤ai≤10^18
输出描述:
输出仅一行,表示数组中有价值的数的个数。
给你一个长度n数组a,问数组中有多少有价值的数?规定若ax为有价值的数,当且仅当:
x左侧存在大于ax的数,右侧存在小于ax的数,论左侧最小的大于ax的数为f,右侧小于ax的最大的数记为g: f为g的倍数。
输入描述:
输入包含两行,第1行仅一个整数n,表示数组的长度接下来一行有n个整数,表示数组a
保证全部数据: 1≤n≤10^5,1≤ai≤10^18
输出描述:
输出仅一行,表示数组中有价值的数的个数。
测试用例:
3
4 3 2
输出1
第二题:
小强有一天想去郊区玩,但是路上会经过一片山路。山路可以看作是一个n * m (n行m列)的网格,每个网格代表一个区域。山路崎岖不平,每一个区域都有一个会消耗的体力值。小强在走山路的时候,只能从一个区域走到相邻的4个(上下左右的网格)区域中的任意一个。每到一个区域,会消耗对应的体力值。小强初始位置在第1行上方,需要去到第n行下方(可以在第1行任意区域作为起点,第n行任意区域作为终点)
小强想找种走法,使得经过山路的总体力值消耗最小。请你帮小强找到这么一条路,并输出最小的总体力值消耗。
输入描述:
第一行包含两个数字n,m,分别代表山路的行数和列数。
接下来有几行,每行m个数字。第i行j列的数字吃,代表对应位置的区域的体力值。
其中1≤n,m ≤ 1000,0< Vi,j≤1000
测试用例:
小强想找种走法,使得经过山路的总体力值消耗最小。请你帮小强找到这么一条路,并输出最小的总体力值消耗。
输入描述:
第一行包含两个数字n,m,分别代表山路的行数和列数。
接下来有几行,每行m个数字。第i行j列的数字吃,代表对应位置的区域的体力值。
其中1≤n,m ≤ 1000,0< Vi,j≤1000
测试用例:
3 3
3 1 3
3 1 0
3 1 3
输出3
3 4
9 9 1 1
9 1 1 9
1 1 9 9
输出4
9 9 1 1
9 1 1 9
1 1 9 9
输出4
第二题的代码,超时了,ac60%
#include "bits/stdc++.h" using namespace std; int dx[4] = {1, 0, 0, -1}; int dy[4] = {0, 1, -1, 0}; int main() { int n, m , t; cin >> n >> m; int a[n][m]; long long dp[n][m]; long long res = INT_MAX; queue<pair<int, int>> q; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { cin >> t; a[i][j] = t; if (i == 0) { q.emplace(i, j); } } } for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (i == 0) { dp[i][j] = a[i][j]; } else dp[i][j] = INT_MAX; } } while (!q.empty()) { int x = q.front().first; int y = q.front().second; q.pop(); if (x == 0) { int tx = x + dx[0]; int ty = y + dy[0]; if (tx >= 0 && tx < n && ty >= 0 && ty < m && (dp[tx][ty] > dp[x][y] + a[tx][ty])) { dp[tx][ty] = dp[x][y] + a[tx][ty]; q.emplace(tx, ty); } } else if (x == n - 1) { } else { for (int i = 0; i < 4; ++i) { int tx = x + dx[i]; int ty = y + dy[i]; if (tx >= 0 && tx < n && ty >= 0 && ty < m && (dp[tx][ty] > dp[x][y] + a[tx][ty])) { dp[tx][ty] = dp[x][y] + a[tx][ty]; q.emplace(tx, ty); } } } } for (int j = 0; j < m; ++j) { res = min(dp[n-1][j], res); } cout << res << endl; return 0; }