力扣10.5
2187. 完成旅途的最少时间
给你一个数组time
,其中 time[i]
表示第 i
辆公交车完成 一趟旅途 所需要花费的时间。
每辆公交车可以 连续 完成多趟旅途,也就是说,一辆公交车当前旅途完成后,可以 立马开始 下一趟旅途。每辆公交车 独立 运行,也就是说可以同时有多辆公交车在运行且互不影响。
给你一个整数 totalTrips
,表示所有公交车 总共 需要完成的旅途数目。请你返回完成 至少 totalTrips
趟旅途需要花费的 最少 时间。
数据范围
1 <= time.length <= 105
1 <= time[i], totalTrips <= 107
分析
二分答案,存在一个时间t,在小于t的时候公交车无论如何都无法完成任务,而大于等于t的时候肯定有一种方法可以完成任务,因此只需要二分查找这个点,注意一下二分查找的写法
//查找满足条件的最小值
while(l<r){
int mid = (l + r) >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
// 满足条件的最大值
while(l < r) {
int mid = (l + r + 1) >> 1;
if(check(mid)) l = mid;
else r = mid - 1;
}
可以这样记
- l = m i d l=mid l=mid时,下一个 m i d = ( l + r + 1 ) / 2 mid=(l+r+1)/2 mid=(l+r+1)/2
- l = m i d + 1 l=mid+1 l=mid+1时,下一个 m i d = ( l + r ) / 2 mid=(l+r)/2 mid=(l+r)/2
代码
typedef long long LL;
class Solution {
public:
bool check(LL mid, vector<int>& time, LL totalTrips) {
LL sum = 0;
for(auto k : time) {
sum += mid / k;
}
return sum >= totalTrips;
}
LL find(LL l, LL r, vector<int>& time, LL totalTrips) {
while(l < r) {
LL mid = (l + r) >> 1;
if(check(mid, time, totalTrips)) r = mid;
else l = mid + 1;
}
return l;
}
long long minimumTime(vector<int>& time, LL totalTrips) {
LL l = 0, r = 1e14 + 5;
LL res = find(l, r, time, totalTrips);
return res;
}
};
1301. 最大得分的路径数目
给你一个正方形字符数组 board
,你从数组最右下方的字符 'S'
出发。
你的目标是到达数组最左上角的字符 'E'
,数组剩余的部分为数字字符 1, 2, ..., 9
或者障碍'X'
。在每一步移动中,你可以向上、向左或者左上方移动,可以移动的前提是到达的格子没有障碍。
一条路径的 「得分」 定义为:路径上所有数字的和。
请你返回一个列表,包含两个整数:第一个整数是 「得分」 的最大值,第二个整数是得到最大得分的方案数,请把结果对 10^9 + 7
取余。
如果没有任何路径可以到达终点,请返回 [0, 0]
。
数据范围
2 <= board.length == board[i].length <= 100
分析
记忆化搜索,令dp[x][y]
表示从(x,y)出发到终点的最大数字和
代码
typedef long long LL;
class Solution {
public:
const static LL N = 105, mod = 1e9 + 7;
int dp[N][N], cnt[N][N];
int dx[3] = {-1, -1, 0};
int dy[3] = {-1, 0, -1};
bool vis[N][N];
int n, m;
LL dfs(int x, int y, vector<string>& board) {
if(dp[x][y]) return dp[x][y];
if(x == 0 && y == 0) return dp[x][y] = 0;
auto& t = dp[x][y];
LL maxx = 0;
for(int i = 0; i < 3; i ++ ) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
if(board[nx][ny] == 'X') continue;
if(vis[nx][ny]) continue;
vis[nx][ny] = true;
LL tmp = dfs(nx, ny, board);
if(tmp > maxx) {
maxx = tmp;
cnt[x][y] = cnt[nx][ny];
} else if(tmp == maxx) {
cnt[x][y] += cnt[nx][ny];
}
cnt[x][y] %= mod;
vis[nx][ny] = false;
}
if(cnt[x][y])
t += maxx;
t %= mod;
if(board[x][y] >= '0' && board[x][y] <= '9')
t += board[x][y] - '0';
// cout << x << " " << y << " " << t << endl;
return t;
}
vector<int> pathsWithMaxScore(vector<string>& board) {
n = board.size();
m = board[0].size();
vis[n - 1][m - 1] = true;
cnt[0][0] = 1;
dfs(n - 1, m - 1, board);
return {dp[n - 1][m - 1], cnt[n - 1][m - 1]};
}
};