模拟即可，注意刚开始设置起征点为 0 0 0，减少边界处理问题。
class Solution {
public:
double calculateTax(vector>& brackets, int income) {
long long ans = 0;
int pre = 0;
for (auto &u : brackets) {
int c = min(income - pre, u[0] - pre);
ans += u[1] * c;
if (income <= u[0]) break;
pre = u[0];
}
return 1.0 * ans / 100.0;
}
};
B.
数字三角形的变种
f
[
i
]
[
j
]
f[i][j]
f[i][j] 表示从第
1
1
1 行到第
i
i
i 行第
j
j
j 个需要的最小路径代价。
f
[
i
]
[
j
]
=
m
i
n
{
f
[
i
−
1
]
[
k
]
+
m
o
v
e
C
o
s
t
[
g
r
i
d
[
i
−
1
]
[
k
]
]
[
j
]
}
+
g
r
i
d
[
i
]
[
j
]
f[i][j]=min{ f[i-1][k]+moveCost[grid[i - 1][k]][j]}+grid[i][j]
f[i][j]=min{f[i−1][k]+moveCost[grid[i−1][k]][j]}+grid[i][j]
注意每次只从上一行转移过来，所以只需要两层即可。
class Solution {
public:
int minPathCost(vector>& grid, vector>& moveCost) {
int n = grid.size(), m = grid[0].size();
vector> f(2, vector(m, 0x3f3f3f3f));
for (int j = 0; j < m; ++j) f[0][j] = grid[0][j];
for(int i = 1; i < n; ++i)
for (int j = 0; j < m; ++j) {
int minv = 0x3f3f3f3f;
for (int k = 0; k < m; ++k)
minv = min(minv, f[i - 1 & 1][k] + moveCost[grid[i - 1][k]][j]);
f[i & 1][j] = minv + grid[i][j];
}
int ans = 0x3f3f3f3f;
for (int j = 0; j < m; ++j) ans = min(ans, f[n - 1 & 1][j]);
return ans;
}
};
C.
显然爆搜，可以加一个剪枝优化，即当已经存在一个学生被分配到的饼干数大于等于答案数时，就可以直接剪掉，因为这不会使得答案更小。
亦或是二分答案，同时可以加上上述优化
直接爆搜剪枝：
class Solution {
public:
int ans;
int n, k;
vector c;
vector sum;
void dfs(int u) {
if (u == n) {
int res = 0;
for (int i = 0; i < k; ++i)
res = max(res, sum[i]);
ans = min(ans, res);
return ;
}
for (int i = 0; i < k; ++i) {
if (sum[i] + c[u] < ans) {
sum[i] += c[u];
dfs(u + 1);
sum[i] -= c[u];
}
}
}
int distributeCookies(vector& cookies, int kk) {
ans = 0x3f3f3f3f;
c = cookies;
k = kk;
n = cookies.size();
sum = vector(k, 0);
dfs(0);
return ans;
}
};
二分答案，check时剪枝优化
class Solution {
public:
int ans;
int n, k;
vector c;
vector sum;
int maxv;
bool dfs(int u) {
if (u == n) {
int res = 0;
for (int i = 0; i < k; ++i)
res = max(res, sum[i]);
return res <= maxv;
}
for (int i = 0; i < k; ++i) {
if (sum[i] + c[u] <= maxv) {
sum[i] += c[u];
bool ok = dfs(u + 1);
sum[i] -= c[u];
if (ok) return true;
}
}
return false;
}
bool check(int v) {
maxv = v;
return dfs(0);
}
int distributeCookies(vector& cookies, int kk) {
ans = 0x3f3f3f3f;
c = cookies;
k = kk;
n = cookies.size();
sum = vector(k, 0);
int L = *max_element(cookies.begin(), cookies.end());
int R = accumulate(cookies.begin(), cookies.end(), 0);
while (L < R) {
int mid = L + R >> 1;
if (check(mid)) R = mid;
else L = mid + 1;
}
return L;
}
};
D.
先计算出字符串 s s s 允许哪些字符交换过来，同时计算有这些字符的串 t t t 多少可以接受 s [ 0 ] s[0] s[0]即可。
class Solution {
public:
long long distinctNames(vector& ideas) {
map mp;
vector c(26, 0);
vector> no(26, vector(26, 0));
for (auto& u : ideas) {
// mp 记录所有 u.substr(1) 的出现过的首字符
mp[u.substr(1)] |= 1 << (u[0] - 'a');
}
for (auto& u : ideas) {
int id = u[0] - 'a';
// c 记录有 u[0] 这个首字符的串的个数
c[id] += 1;
int x = mp[u.substr(1)];
for (int j = 0; j < 26; ++j)
// no 记录所有向外提供 u[0]，但是不接受字符 (j+'a')的串的个数
if (x >> j & 1) no[id][j] += 1;
}
int n = ideas.size();
long long ans = 0;
for (int i = 0; i < n; ++i) {
int x = (1 << 26) - 1 - mp[ideas[i].substr(1)];
for (int j = 0; j < 26; ++j)
// 计算所有可以提供 (j+'a') 的同时可以接受 ideas[i][0]的串的个数
if (x >> j & 1) ans += c[j] - no[j][ideas[i][0] - 'a'];
}
return ans;
}
};
