力扣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=mid$时，下一个 $mid=(l+r+1)/2$
• $l=mid+1$时，下一个$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]};}
};