程序员进阶之算法练习（六十六）
题目1
题目链接 题目大意： n个黑球，m个红球，将这些球分成若干堆，要求： 1、每一堆都有至少一个黑球； 2、每一堆都有至少一个红球； 3、每一堆的黑球和红球数量差不超过d；
输入： 第一行是整数 𝑡，表示t个样例 (1≤𝑡≤1000) 每个样例一行，整数 𝑟, 𝑏, and 𝑑 (1≤𝑟,𝑏≤1e9; 0≤𝑑≤1e9)
输出： 如果可以按照要求拆分，则输出YES；如果无法拆分，则输出NO；
Examples input 4 1 1 0 2 7 3 6 1 4 5 4 0
output YES YES NO NO
题目解析： 用贪心的思想，在满足1和2的情况下，球堆的数量越多，那么3更容易满足； 那么就可以直接分出min(n, m)堆，然后剩下的球再平分到这些球堆中，最后再计算是否满足条件3。 为了方便计算，我们可以假设n<m；（如果n>m则进行调换，红黑色并不影响） 那么会有m堆，每堆最多有球(n+m-1)/m个，这样就可以快速计算是否满足条件3。
class Solution {
static const int N = 105;
public:
int n, m, k, t;
public:
void solve() {
cin >> t;
while (t--) {
cin >> n >> m >> k;
if (n < m) {
swap(n, m);
}
cout << (((n + m - 1) / m - 1) <= k ? "YES" : "NO") << endl;
}
}
}
ac;题目2
题目链接 题目大意： 在一个n x m的网格中，小明现在站在[1, 1]的位置，想要走到[n, m]； 当小明在位置[x, y]时，每次可以选择： 走到[x, y+1]，花费x的代价； 走到[x+1,y]，花费y的代价； 问，小明能否走到位置[n, m]并花费的代价和刚好是k；
输入： 第一行是整数𝑡，表示样例数 (1≤𝑡≤100) 每个样例一行，整数 𝑛, 𝑚, and 𝑘 (1≤𝑛,𝑚≤100; 0≤𝑘≤10000)
输出： 每个样例一行，可以则输出YES；不可以则输出NO；
Examples input 6 1 1 0 2 2 2 2 2 3 2 2 4 1 4 3 100 100 10000
output YES NO YES NO YES NO
题目解析： 对于一个4x4的格子，我们有随便选择一种走法 1 0 0 0 2 0 0 0 3 4 5 6 0 0 0 7 这种走法的步伐是： (1,1) - (2,1) - (3,1) - (3,2) - (3,3) - (3,4) - (4,4)
再随机选择一种走法 1 2 3 4 0 0 0 5 0 0 0 6 0 0 0 7 这种走法的步伐是： (1,1) - (1,2) - (1,3) - (1,4) - (2,4) - (3,4) - (4,4)
容易知道，第一种的代价是1+1+3+3+3+4，都是步伐组合中数字的一半； 第二种的代价是1+1+1+4+4+4，都是步伐组合中数字的一半；
我们知道步伐的组合，本质就是6次选择，每次选择x=x+1或者y=y+1，一共有C(6,3)种可能；（从6个元素中选择3个元素的可能） 计算几次，发现价格是一样的。
怎么证明呢？ 我们用dp[i][j]表示，走到i、j的代价，容易知道dp[i][j+1]=dp[i][j]+i 以及 dp[i+1][j]=dp[i][j]+j，并且在边界情况是唯一解； 那么dp[i+1][j+1]=dp[i][i+1]+j=dp[i][j]+i+j。 我们由dp[1][1]开始，可以递推出来dp[1100][1100]的价格。
思考🤔： 这里也可以用数学方式去解，但用dp会更直观一些。
class Solution {
static const int N = 105;
public:
int n, m, k, t;
int dp[N][N];
public:
void solve() {
cin >> t;
dp[1][1] = 0;
for (int i = 2; i < N; ++i) {
dp[1][i] = dp[1][i - 1] + 1;
dp[i][1] = dp[i-1][1] + 1;
}
for (int i = 2; i < N; ++i) {
for (int j = 2; j < N; ++j) {
dp[i][j] = dp[i-1][j] + j;
}
}
while (t--) {
cin >> n >> m >> k;
cout << (dp[n][m] == k ? "YES" : "NO") << endl;
}
}
}
ac;题目3
题目链接 题目大意： 有n个学生想参加比赛，每个学生都有一个自己的学校u[i]，以及能力强度s[i]； 现在已知，假如主办方决定队伍人数是k人一队，则每个学校会按照能力高低，从高开始组队（k个人一队），如果剩余不足k人，则放弃； 问：当k=1、2、3... k的时候，能参加比赛的人，总的能力强度分别是多少。
输入： 第一行整数t，表示有t个样例（1≤𝑡≤1000） 每个样例第一行是整数 𝑛 (1≤𝑛≤2⋅1e5) 第二行是整数𝑢1,𝑢2,…,𝑢𝑛 (1≤𝑢𝑖≤𝑛) 第三行是𝑠1,𝑠2,…,𝑠𝑛 (1≤𝑠𝑖≤1e9) 输出： 每个样例一行，分别输出k个整数，表示当k=1、2、3... k的时候的总能力强度。
Examples input 4 7 1 2 1 2 1 2 1 6 8 3 1 5 1 5 10 1 1 1 2 2 2 2 3 3 3 3435 3014 2241 2233 2893 2102 2286 2175 1961 2567 6 3 3 3 3 3 3 5 9 6 7 9 7 1 1 3083 output 29 28 26 19 0 0 0 24907 20705 22805 9514 0 0 0 0 0 0 43 43 43 32 38 43 3083
题目解析： 先按照学校分类，然后排期得到每个学校能力从小到大的数据； => 极端情况所有人都是同一个学校，复杂度O（NlogN）。 接下来计算k=1.2.3....n的时候，所有学生的能力值。 对于某个学校（学生人数是count[i]），我们知道最终无法组成队伍的人有count[i]%k，也就是前k个； 那么对于k=t，将所有学校排序后的前(count[i]%t)数字累加起来，就是所有无法参加比赛人之和。
注意： 由于k很多种情况，学校也可能有很多个，这里需要注意实现方式，否则很容易超时。 1、只枚举存在的学校；（不需要从1到n去枚举，这个通过map可以实现） 2、每个学校，在枚举k=1.2.3...n的时候，只需要考虑到k=学校人数即可；（由于所有学校的总人数=n，所以k枚举的总次数=n）
class Solution {
static const int N =200010;
public:
int n, m;
int u[N], s[N];
lld ans[N], sum[N];
map<int, vector<lld>> h;
public:
void solve() {
int t;
cin >> t;
while (t--) {
cin >> n;
h.clear();
for (int i = 0; i < n; ++i) {
cin >> u[i];
ans[i+1] = 0;
sum[i+1] = 0;
}
for (int i = 0; i < n; ++i) {
cin >> s[i];
sum[u[i]] += s[i];
h[u[i]].push_back(s[i]);
}
for (map<int, vector<lld>> ::iterator it = h.begin(); it != h.end(); ++it) {
sort(it->second.begin(), it->second.end());
vector<lld> tmp;
tmp.push_back(0);
for (int i = 1; i <= it->second.size(); ++i) {
ans[i] += sum[it->first];
tmp.push_back(tmp[i-1] + it->second[i-1]);
if (it->second.size()%i) {
ans[i] -= tmp[it->second.size() % i];
}
}
}
for (int i = 1; i <= n; ++i) {
cout << ans[i] << " ";
}
cout << endl;
}
}
}
ac;题目4
题目链接
题目大意：
给出n个整数的数组a和b，数组a和数组b的乘积和等于a[0]*b[1]+a[2]*b[2]+...+a[n]*b[n]；
可以选择一个区间[x, y]（x<=y)，调转数组a区间[x, y]内整数的顺序，比如说数字1,2,3则调转为3,2,1；
求调转之后，数组a和数组b的最大乘积和。
输入： 第一行是整数n，表示数组长度 (1≤𝑛≤5000) 第二行是n个整数a[1]、a[2]、a[3]... a[n]; (1<=a[i] <= 1e7）； 第二行是n个整数b[1]、b[2]、b[3]... b[n];(1<=b[i] <= 1e7）；
输出： 调转一次区间之后，数组a和数组b的最大乘积和。
Examples input 5 2 3 2 1 3 1 3 2 4 2
output 29
样例解释： 调转区间[4,5]，a=[2,3,2,3,1]，那么数组a和b的成绩和= 2⋅1+3⋅3+2⋅2+3⋅4+1⋅2=29
题目解析： 先不考虑复杂度，一个直接的做法便是枚举区间，然后计算数字相乘和； 这样的复杂度是O（N^3）；
做一些简单的优化： 将求和的过程拆成三部分，假设revert的区间是[x, y]，那么[1, x)和(y, n]部分是可以预处理的；（前i个数字相乘和、后i个数字相乘和） 问题在于，revert的区间[x, y]如何快速计算？ 尝试从[x, y]去推导[x, y+1]和[x-1, y]的数字相乘和，发现都需要O（N）的时间去计算； 后面发现从[x, y]去推导[x-1, y+1]就简单了很多。
那么这个题目可以用O（N^2）的空间，来减少O（N）的时间复杂度，使得时间、空间复杂度都控制在O（N^2），在题目可接受范围内。
注意： 题目的核心在于计算revert(i, j)区间数字相乘和，由于推导的时候每次区间都会+2大小，所以需要推导区间[i, i]和[i, i+1]两次。
class Solution {
static const int N =5001;
public:
int n;
lld a[N], b[N];
lld sumLeft[N], sumRight[N], sumRevert[N][N];
public:
void solve() {
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
for (int i = 0; i < n; ++i) {
cin >> b[i];
}
sumLeft[0] = a[0] * b[0];
for (int i = 1; i < n; ++i) {
sumLeft[i] = sumLeft[i - 1] + a[i] * b[i];
}
sumRight[n - 1] = a[n - 1] * b[n - 1];
for (int i = n - 2; i >= 0; --i) {
sumRight[i] = sumRight[i + 1] + a[i] * b[i];
}
for (int i = 0; i < n; ++i) {
// 推导[i, i]=>[i-1, i+1]
int left, right;
sumRevert[i][i] = a[i] * b[i];
left = i - 1, right = i + 1;
while (left >= 0 && right < n) {
sumRevert[left][right] = sumRevert[left + 1][right - 1] + a[left] * b[right] + b[left] * a[right];
--left;
++right;
}
left = i, right = i + 1;
if (right < n) {
sumRevert[left][right] = a[left] * b[right] + b[left] * a[right];
while(true) {
--left;
++right;
if (left < 0 || right >= n) {
break;
}
sumRevert[left][right] = sumRevert[left + 1][right - 1] + a[left] * b[right] + b[left] * a[right];
}
}
}
lld ans = sumLeft[n - 1];
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
// revert的区间为[i, j]
lld tmp = 0;
if (i > 0) {
tmp += sumLeft[i - 1];
}
if (j + 1 < n) {
tmp += sumRight[j + 1];
}
tmp += sumRevert[i][j];
ans = max(ans, tmp);
}
}
cout << ans << endl;
}
}
ac;题目5
题目链接 题目大意： 一棵树有n个节点，每一条边有一个价值，等于两边节点的差的绝对值； 每个节点有两个值l[i]和r[i]，节点的值x[i]需要满足l[i] <= x[i] <= r[i]; 现在问，按照要求分配各个节点的值，这棵树所有边的最大的价值是多少。
输入： 第一行是整数t，表示有t个样例 (1≤𝑡≤250). 每个样例第一行是整数 𝑛 (2≤𝑛≤1e5)； 接下来n行，每行两个整数𝑙𝑖 and 𝑟𝑖 (1≤𝑙𝑖≤𝑟𝑖≤1e9). 接下来n-1行，每行两个整数𝑢 and 𝑣，表示u到v有一条边 (1≤𝑢,𝑣≤𝑛, 𝑢≠𝑣) 输出： 每一个样例一行，输出最大的价值数。
Examples input 3 2 1 6 3 8 1 2 3 1 3 4 6 7 9 1 2 2 3 6 3 14 12 20 12 19 2 12 10 17 3 17 3 2 6 5 1 5 2 6 4 6 output 7 8 62
样例解释：
题目解析： 只考虑一条边的情况，假设两边的节点取值范围是[L1, R1]和[L2, R2] 可以知道，这条边的价值只有两种情况：(L1 - R2) 或者(R1 - L1）。
对于每一个点，我们存两个值：ans[i][0]表示取节点i的value取最小值的子树价值，ans[i][1]表示取最大值的子树价值。我们从根节点开始遍历这棵树，对于每一个节点u，其ans[u][0]是由多个子树的ans[v][0]+value(u, v)或者ans[v][1]+value(u, v) 组成。
这样只需从根节点1开始dfs整颗树，那么根节点的ans[1][0]或者ans[1][1]就是最大价值。
class Solution {
static const int N = 200010;
public:
vector<int> g[N];
bool vis[N];
lld val[N][2];
lld ans[N][2];
void dfs(int u) {
vis[u] = 1;
for (int i = 0; i < g[u].size(); ++i) {
int v = g[u][i];
if (!vis[v]) {
dfs(v);
ans[u][0] += max(ans[v][0] + abs(val[v][0] - val[u][0]), ans[v][1] + abs(val[v][1] - val[u][0]));
ans[u][1] += max(ans[v][0] + abs(val[v][0] - val[u][1]), ans[v][1] + abs(val[v][1] - val[u][1]));
}
}
}
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
g[i].clear();
vis[i] = 0;
ans[i][0] = ans[i][1] = 0;
}
for (int i = 1; i <= n; ++i) {
// cin >> val[i][0] >> val[i][1];
scanf("%d%d", &val[i][0], &val[i][1]);
}
for (int i = 0; i < n - 1; ++i) {
int u, v;
// cin >> u >> v;
scanf("%d%d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1);
cout << max(ans[1][0], ans[1][1]) << endl;
}
}
}
ac;腾讯云开发者
