二分算法、贪心思想实现优化
题目描述
David 作为一名 scut 的大学生，自然需要去学习。
在 scut，有 N 门不同的课程，一个学期一共有 M 周，对于每一周，会上 N 次课，每一门课程恰好一周上一次课，David 对于每一个课程都有一个熟练度，初始时都为 0。
对于一节课 David 可以选择如下选项中的一个：
去上课：如果他上的是第 i 门课，那么他对于这节课的熟练度增加 Ai。
翘课：David 热爱学习，所以他会选一门课自学，如果他选了第 i 门课，那么他对于这节课的熟练度增加 Bi。
为了去更多的学习课外知识，David 不会在课下学习这 N 门课程，但是他又不想要让自己挂科，于是他找到了你，他想让自己对每一门课的熟练度的最小值最大。
输入格式
第一行两个整数 N,M
接下来一行 N 个整数 Ai。
接下来一行 N 个整数 Bi。
输出格式
仅输出一行一个整数表示你的答案。
样例数据
输入
3 3
19 4 5
2 6 2
输出
18
是c还是java
#include <stdio.h>
#include <stdlib.h>
// 比较函数，用于快速排序
int cmp(const void* a, const void* b) {
return *(int*)a - *(int*)b;
}
int main() {
int N, M;
scanf("%d %d", &N, &M);
int* A = (int*)malloc(N * sizeof(int));
int* B = (int*)malloc(N * sizeof(int));
for (int i = 0; i < N; i++) {
scanf("%d", &A[i]);
}
for (int i = 0; i < N; i++) {
scanf("%d", &B[i]);
}
// 按照课程 i 的 B[i] - A[i] 从大到小排序
// 这样选择翘课时优先选择 B[i] 大的课程
// 避免使用贪心思想时选择导致最小值最大的方案
int* diff = (int*)malloc(N * sizeof(int));
for (int i = 0; i < N; i++) {
diff[i] = B[i] - A[i];
}
qsort(diff, N, sizeof(int), cmp);
// 统计一共有多少个正数和负数
int positive = 0, negative = 0;
for (int i = 0; i < N; i++) {
if (diff[i] > 0) {
positive++;
}
else if (diff[i] < 0) {
negative++;
}
}
// 选择使得熟练度最小的方案
int minSkill = 0;
if (positive <= M) {
// 如果正数的个数小于等于 M
// 那么可以选择所有正数，剩下的 M - positive 个位置选择差值最小的负数
for (int i = 0; i < positive; i++) {
minSkill += A[i];
}
for (int i = positive; i < N; i++) {
minSkill += B[i];
}
if (M > positive) {
qsort(A, N, sizeof(int), cmp); // 将 A 数组重新排序
for (int i = 0; i < M - positive; i++) {
minSkill += A[i];
}
}
}
else {
// 如果正数的个数大于 M
// 那么只能选择使得差值最小的前 M 个正数
for (int i = 0; i < M; i++) {
minSkill += A[i];
}
}
free(A);
free(B);
free(diff);
printf("%d\n", minSkill/2);
return 0;
}
什么开发语言???
- 这有个类似的问题, 你可以参考下: https://ask.csdn.net/questions/7798835
- 除此之外, 这篇博客: C语言实现八大排序算法详解及其性能之间的中的 名字已经暴露了他的算法，就是往里面插入数据，就拿我们生活中的例子来说，打扑克牌。我们往手里码牌的时候，是一张一张的码，先码一张，抓手心，不需要修改位置，因为只有一张牌，一定是有序的。再接一张，和手里的牌对比大小，调整位置，选择放在它的左边或者右边。然后接着码，又接到一张牌，拿到先和右边的牌比，比右边还大就放到最右边，如果比右边这张小呢，在和左边这张比。同样，我们这里也是这样的，首先我们默认第一个元素，一定是有序，OK吧。然后第二个，元素比较，大，放到左边，小放到右边。然后第三个元素，直到第N个，比它前一个大，继续往前找位置，直到找到对应位置了，就是有序数列了。（当然每次找位置都是在一个有序的序列中找，所以完全可以用二分查找找位置，数据大的话，二分明显快于我们一张一张比） 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
算法思想
代码写出来了，但是
样例数据
输入
3 3
19 4 5
2 6 2
输出
18
这个问题可以使用动态规划的方法进行求解。我们可以定义一个二维数组 dp，其中 dp[i][j] 表示在第 j 周结束时，对于第 i 门课程的熟练度的最小值最大。
假设当前是第 j 周，我们需要考虑在这一周的最后一节课，是选择去上课还是翘课。
如果选择去上课，那么对于第 i 门课程的熟练度的增加为 A[i]，同时第 i 门课程的熟练度最小值最大也会受到限制，我们需要从前一周结束时的熟练度最小值最大中选择一个最大值作为当前的状态。因此，状态转移方程为：
dp[i][j] = max(dp[i][j], dp[i][j-1] + A[i])
如果选择翘课，那么对于第 i 门课程的熟练度的增加为 B[i]，同时第 i 门课程的熟练度最小值最大不会受到限制，我们可以直接加上 B[i]。因此，状态转移方程为：
dp[i][j] = max(dp[i][j], dp[i-1][j-1] + B[i])
最终的答案为 dp[N][M]，即在最后一周结束时，对于每一门课程的熟练度的最小值最大。
以下是Python的实现代码：
N, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
dp = [[0] * (M + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
for j in range(1, M + 1):
dp[i][j] = max(dp[i][j], dp[i][j-1] + A[i-1])
dp[i][j] = max(dp[i][j], dp[i-1][j-1] + B[i-1])
print(dp[N][M])
对于给定的样例数据，输出结果为 18。
最长上升子序列优化（贪心+二分）（超级详细的讲解）
可以学习下，超详细
对于每一门课程，如果自学比去上课得到的熟练度更高，则选择自学。否则，选择去上课。具体来说，对于第 i 门课程，如果 Bi >= Ai，则选择自学。否则，选择去上课。这样，可以保证对每一门课程的熟练度的最小值最大。以下是 Python 代码实现：
n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
min_vals = [0] * n
for i in range(n):
if b[i] >= a[i]:
min_vals[i] = b[i]
else:
min_vals[i] = a[i]
max_min_val = min(min_vals)
print(max_min_val * m)
先使用二分算法来查找最小值，假设最小值为 x，然后用贪心思想来判断是否存在一种安排方案，使得每门课的熟练度都大于等于 x。
来自GPT的回答：
这个问题可以通过使用二分算法和贪心思想来实现优化。
首先，我们可以使用二分算法确定最小的熟练度值。设定一个左边界 l 和右边界 r，初始时 l = 0，r = max(Ai) * M，其中 max(Ai) 表示所有课程的最大熟练度增加值。然后在每次二分的过程中，取中间值 mid = (l + r) // 2，作为当前熟练度的候选值。接下来，使用贪心思想判断是否存在一种选课方案，使得每门课程的熟练度都大于等于 mid。如果存在这样的方案，则更新左边界 l = mid + 1；否则，更新右边界 r = mid - 1。不断迭代直到左边界 l 大于右边界 r。
在每次二分过程中，使用贪心思想来判断是否存在满足条件的选课方案。具体做法如下：
初始化每门课程的当前熟练度为 0。
对于每周的选课情况，优先选择上课选项，即选择增加熟练度最多的课程（Ai 最大）。如果上课选项无法使某门课程的熟练度达到当前熟练度候选值 mid，则选择翘课选项，即选择增加熟练度次多的课程（Bi 次大）。
如果所有课程的熟练度都大于等于 mid，说明当前的熟练度候选值可行，更新左边界 l = mid + 1；否则，更新右边界 r = mid - 1。
最终，当二分算法结束时，左边界 l 的值就是最大的满足条件的最小熟练度值，即为答案。
以下是实现该算法的示例代码：
python
Copy code
def can_reach_min_skill(mid, A, B, M):
curr_skill = [0] * len(A)
for _ in range(M):
max_increase = max(A[i] for i, skill in enumerate(curr_skill) if skill < mid)
max_idx = [i for i, skill in enumerate(curr_skill) if skill < mid and A[i] == max_increase]
if max_idx:
max_idx = max_idx[0]
curr_skill[max_idx] += max_increase
else:
min_increase = min(B[i] for i, skill in enumerate(curr_skill) if skill < mid)
min_idx = [i for i, skill in enumerate(curr_skill) if skill < mid and B[i] == min_increase]
if min_idx:
min_idx = min_idx[0]
curr_skill[min_idx] += min_increase
else:
return False
return all(skill >= mid for skill in curr_skill)
def find_min_skill(N, M, A, B):
l = 0
r = max(A) * M
while l <= r:
mid = (l + r) // 2
if can_reach_min_skill(mid, A, B, M):
l = mid + 1
else:
r = mid - 1
return r
# 输入处理
N, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
# 调用函数求解
answer = find_min_skill(N, M, A, B)
# 输出结果
print(answer)
注意，以上代码假设输入数据是合法的，没有进行过多的错误检查。你可以根据实际情况进行适当的错误处理和输入验证。
这个问题可以使用贪心算法来解决。贪心算法的思想是每次选择当前最优的解，然后逐步构建整体最优解。
首先，我们需要确定每一周 David 上哪门课程。对于每一周，他可以选择上课或者翘课。为了使得每门课程的熟练度最小值最大，我们应该优先选择那些 Ai - Bi 最大的课程，即每周上课。如果 Ai - Bi 相同，则可以任意选择上课或者翘课。
具体的算法步骤如下：
- 将所有课程按照 Ai - Bi 的值从大到小进行排序。
- 遍历每一周，对于每一周，选择当前剩余课程中 Ai - Bi 最大的课程进行上课，同时更新该课程的熟练度。
- 计算所有课程的熟练度的最小值。
下面是C++的示例代码实现：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int N, M;
cin >> N >> M;
vector<int> A(N), B(N);
for (int i = 0; i < N; i++) {
cin >> A[i];
}
for (int i = 0; i < N; i++) {
cin >> B[i];
}
vector<pair<int, int>> diff(N);
for (int i = 0; i < N; i++) {
diff[i] = make_pair(A[i] - B[i], i);
}
sort(diff.rbegin(), diff.rend());
int minSkill = 0;
for (int i = 0; i < M; i++) {
minSkill += A[diff[i].second];
}
cout << minSkill << endl;
return 0;
}
这段代码首先读取输入的 N 和 M，然后分别读取每门课程的 Ai 和 Bi。接下来，将每门课程的 Ai - Bi 存储在一个数组中，并按照从大到小的顺序进行排序。然后，遍历每一周，选择当前剩余课程中 Ai - Bi 最大的课程进行上课，并累加该课程的熟练度。最后，输出所有课程的熟练度的最小值。
对于给定的示例数据，输出结果为 18。
回答部分参考、引用ChatGpt以便为您提供更准确的答案：
要将QQ号码或二维码做成链接，使得在手机端点击链接可以直接添加好友，可以按照以下步骤进行操作：
- 生成链接：首先，您需要将QQ号码或者二维码转化为链接的形式。可以使用HTML语言编写一个简单的超链接，将QQ号码作为参数添加到链接中。例如，链接格式可以是
https://wpa.qq.com/msgrd?v=3&uin=<QQ号码>&site=qq&menu=yes，其中<QQ号码>是您的QQ号码。 - 链接展示：您可以将生成的链接嵌入到网页、邮件或其他应用中，使得用户可以点击链接访问。在手机端，用户点击链接后，会自动跳转到QQ的添加好友页面，并显示对应的QQ号码，用户只需确认添加即可。
请注意，生成链接的方式可能因不同的应用或开发环境而略有不同。您可以根据具体需求和技术背景进行适当的调整和修改。