class Solution {public: double calculateTax(vector<vector<int>>& bs, int ie) { double ret = 0; bs.push_back({0, 0}); sort(bs.begin(), bs.end(), [](vector<int>& a, vector<int>& b) { return a[0] < b[0]; }); for (int i = 0; i < bs.size(); ++ i) { // cout << ie << " " << bs[i + 1][0] << " " << bs[0] << endl; if (i == bs.size() - 1) { }else { if (ie >= bs[i + 1][0]) { ret += (double)(bs[i + 1][0] - bs[0]) * bs[i + 1][1] / 100; }else { ret += ((double)ie - bs[0]) * bs[i + 1][1] / 100; break; } } // cout << ret << endl; } return ret; }};第二题
解法:线性 DP
dist 体现 i 这个点到最底层的间隔
时间复杂度 O(N * M ^ 2)
空间复杂度 O(N)
class Solution { public: unordered_map<int, int> row; int dist[3000]; int n, m; int minPathCost(vector<vector<int>>& grid, vector<vector<int>>& mt) { vector<int> one, last; for (int i = 0; i < grid.size(); ++ i) { for (int& j : grid) { row[j] = i; if (i == 0) one.push_back(j); if (i == grid.size() - 1) last.push_back(j); } } memset(dist, 0x3f, sizeof dist); for (int& x : last) dist[x] = 0; int n = grid.size(); for (int i = n - 2; i >= 0; -- i) { for (int j = 0; j < grid.size(); ++ j) { int x = grid[j]; for (int k = 0; k < grid[i + 1].size(); ++ k) { int v = grid[i + 1][k]; dist[x] = min(dist[x], v + mt[x][k] + dist[v]); // dist[x] += dist[v]; } } } int ret = 1e9; // cout << dist[0] << " " << dist[4] << endl; for (int& i : one) { // cout << i << " " << dist << endl; ret = min(ret, dist + i); } return ret; }};第三题
解法 1： 回溯
搜索每包零食分给每个朋侪, 每包零食有 K 种选择；
时间复杂度 O(N ^ k)
空间复杂度 O(N)
class Solution { int n, K, ans; vector<int> A, tot; void dfs(int d) { if (d == n) { // 全部零食都分完了，盘算小朋侪得到的最大饼干数 int t = tot[0]; for (int i = 1; i < K; i++) t = max(t, tot); // 全部结果里取最小 ans = min(ans, t); return; } for (int i = 0; i < K; i++) { // 枚举第 d 包零食分给第 i 个小朋侪 tot += A[d]; dfs(d + 1); // 打消修改 tot -= A[d]; } }public: int distributeCookies(vector<int>& cookies, int k) { n = cookies.size(); K = k; A = cookies; tot.resize(K, 0); ans = 1e9; dfs(0); return ans; }};作者：TsReaper链接：https://leetcode.cn/circle/discuss/4GGKMb/view/OxXY76/泉源：力扣（LeetCode）著作权归作者全部。商业转载请接洽作者得到授权，非商业转载请注明出处。解法2：二分 + 回溯
二分最大不公上限，回溯是否有满意此上限的分配方案
