AI刷题-蛋糕工厂产能规划、优质章节的连续选择

挑两个简单的写写

目录

一、蛋糕工厂产能规划

问题描述

输入格式

输出格式

解题思路： 

问题理解

数据结构选择

算法步骤

关键点

最终代码：

运行结果：​编辑 

二、优质章节的连续选择 

问题描述

输入格式

输出格式

解题思路：

问题理解

数据结构选择

算法步骤

最终代码：

运行结果： 

 

 

 

---

一、蛋糕工厂产能规划

问题描述

小明开了一家蛋糕工厂，目前工厂里面有 m 台机器和 w 个工人，每天可以生产的蛋糕数量是 m * w。有一天他接到了一个订单，需要生产 n 个蛋糕，客户希望能够尽快的一次性交付，但是他算不清楚需要多少天才能生产完，请你帮帮小明。（提示：为了提升产能，每天可以用蛋糕购买额外的机器或者工人，每台机器或者每个工人，需要花费 p 个蛋糕。）

为了方便理解，我们举个例子：假如最开始小明的工厂只有 m = 1 台机器和 w = 2 个工人，每次扩大产能需要的花费是 p = 1，为了生产 n = 60 个蛋糕，可以这么操作：

• 第一天：m * w = 1 * 2 = 2 生产 2 个蛋糕，同时新增 2 台机器，此时 m = 3，剩余蛋糕 0

• 第二天：m * w = 3 * 2 = 6 生产 6 个蛋糕，同时新增 3 台机器，3 个工人，此时 m = 6, w = 5，剩余蛋糕 0

• 第三天：m * w = 6 * 5 = 30

• 第四天：m * w = 6 * 5 = 30 所以在第四天就完成了生产计划

输入格式

输入的数据只有一行，空格分割的四个整数，代表 m, w, p, n

数据约束

• 1 <= m, w, p, n <= 10^8

输出格式

输出一个整数用来表示需要几天才能完成生产计划

输入样例

3 1 2 12

输出样例

3

样例解释

• 第一天：生产的蛋糕数量 m * w = 3 * 1 = 3。此时花 2 个蛋糕，雇佣了另外一个工人，此时 w = 2，依然剩余 1 个蛋糕

• 第二天：生产的蛋糕数量 3 * 2 = 6。此时花 2 * p = 4 个蛋糕雇佣了另外一个工人，同时新增了另外一台机器，此时 m = 4, w = 3，而且剩余 3 个蛋糕（包括第一天剩余的那一个）

• 第三天：生产的蛋糕数量 4 * 3 = 12，已经符合预期的产量了，所以只需要三天就可以完成生产计划

解题思路： 

问题理解

小明的蛋糕工厂每天可以生产 m * w 个蛋糕。为了尽快完成生产 n 个蛋糕的任务，他可以选择用蛋糕购买额外的机器或工人，每台机器或每个工人需要花费 p 个蛋糕。目标是计算出最少需要多少天才能完成生产计划。

数据结构选择

由于我们需要动态地调整机器和工人的数量，并且需要计算每天的生产量和剩余蛋糕数，因此我们可以使用一个循环来模拟每一天的生产过程。

算法步骤

1. 初始化：

   • 初始机器数量 m
   • 初始工人数量 w
   • 每天的生产成本 p
   • 目标生产量 n
   • 当前天数 days
   • 当前剩余蛋糕数 cakes

2. 循环模拟每一天：

   • 计算当天的生产量 production = m * w
   • 更新剩余蛋糕数 cakes += production
   • 检查是否已经达到目标生产量 n，如果是，则返回当前天数 days
   • 计算可以购买的机器和工人的最大数量 max_buy = cakes / p
   • 尝试用剩余的蛋糕购买机器和工人，使得 m * w 最大化
   • 更新机器和工人的数量
   • 增加一天 days++

3. 返回结果：

   • 当达到或超过目标生产量 n 时，返回当前天数 days

关键点

• 在每次购买机器和工人时，需要考虑如何分配购买的资源，使得 m * w 最大化。
• 需要动态调整机器和工人的数量，以确保每天的生产量最大化。

 

最终代码：

#include <iostream>
#include <algorithm>
#include <limits>int solution(int m, int w, int p, int n) {int passes = 0;long long candy = 0;  // 使用 long long 防止溢出long long run = std::numeric_limits<long long>::max();while (candy < n) {if (m > std::numeric_limits<long long>::max() / w) {break;} else {int step = (p - candy) / (m * w);if (step <= 0) {int mw = candy / p;if (m >= w + mw) {w += mw;} else if (w >= m + mw) {m += mw;} else {int total = m + w + mw;m = total / 2;w = total - m;}candy %= p;step = 1;}passes += step;if (step * m > std::numeric_limits<long long>::max() / w) {candy = std::numeric_limits<long long>::max();} else {candy += step * m * w;run = std::min(run, static_cast<long long>(passes) + ((n - candy + m * w - 1) / (m * w)));}}}return std::min(passes, static_cast<int>(run));
}int main() {std::cout << (solution(3, 1, 2, 12) == 3) << std::endl;std::cout << (solution(10, 5, 30, 500) == 8) << std::endl;std::cout << (solution(3, 5, 30, 320) == 14) << std::endl;return 0;
}

运行结果： 

二、优质章节的连续选择 

问题描述

番茄小说上有很多精彩的书籍，编辑想从其中一本书籍中挑选出若干精彩章节。这本书有 n 个章节，每个章节的文字数量分别为 a[i]（1≤i≤n）。

出于阅读体验的考虑，编辑希望挑选出来的章节是在书中是连续的，并且总字数不超过 k。

编辑是特别的书虫，他认为在挑选出来的章节中，如果某个章节的文字数量比前后章节都多，则这个章节是优质章节。挑选出来章节中的第一章和最后一章不能作为优质章节。

编辑想知道，如何挑选才能产生尽可能多的优质章节，并且满足总字数不超过 k。

输入格式

第一行是整数 n 和 k；（3≤n≤10^5，0≤k≤10^9）

第二行是 n 个整数 a[i]；（1≤a[i]≤10^7）

输出格式

输出整数 m、start、end，m 表示优质章节的数量，start 表示挑选出来的首个章节在书中的位置，end 是挑出来的末尾章节在书中的位置；

如果优质章节数量相同的选择有多个，则输出总字数最少的选择；如果仍有多个，则输出 start 最小的选择；

题目保证至少有一种选择。

输入样例 1

8 15000

1000 3000 2000 4000 3000 2000 4000 2000

输出样例 1

2 1 5

输入样例 2

8 15000

2000 5000 2000 1000 4000 2000 4000 3000

输出样例 2

2 4 8

样例解释

样例 1，选择第 1 章到第 5 章，一共有 2 个优质章节，分别是第 2 章和第 4 章；

样例 2，选择第 4 章到第 8 章，一共有 2 个优质章节，分别是第 5 章和第 7 章；

数据范围

（3≤n≤10^5，0≤k≤10^9）

（1≤a[i]≤10^7）

 

解题思路：

问题理解

1. 目标：从一本书的连续章节中挑选出总字数不超过 k 的章节，使得优质章节（比前后章节字数都多的章节）的数量最多。
2. 约束：
   • 章节必须是连续的。
   • 总字数不超过 k。
   • 优质章节不能是挑选出来的第一个或最后一个章节。

数据结构选择

• 数组：用于存储每个章节的字数。
• 滑动窗口：用于在数组中寻找满足条件的连续子数组。

算法步骤

1. 初始化：

   • 使用两个指针 start 和 end 来表示当前窗口的开始和结束位置。
   • 使用变量 current_sum 来记录当前窗口的总字数。
   • 使用变量 best_start 和 best_end 来记录最优解的开始和结束位置。
   • 使用变量 best_quality_count 来记录最优解中的优质章节数量。

2. 滑动窗口：

   • 从左到右遍历数组，逐步扩展 end 指针，直到总字数超过 k。
   • 当总字数超过 k 时，移动 start 指针，直到总字数再次小于等于 k。
   • 在每次移动 end 指针时，检查当前窗口内的优质章节数量，并更新最优解。

3. 优质章节判断：

   • 对于每个窗口，遍历其中的章节，判断是否为优质章节（比前后章节字数都多）。
   • 注意：第一个和最后一个章节不能作为优质章节。

4. 结果输出：

   • 最终输出最优解的优质章节数量、开始位置和结束位置。

最终代码：

#include <bits/stdc++.h>std::string solution(int n, int k, std::vector<int> array_a) {assert(n == array_a.size());assert(3 <= n && n <= 1e5);assert(0 <= k && k <= 1e9);std::vector<long long> sum_array(n);sum_array[0] = array_a[0];for (int i = 1; i < n; ++i) {sum_array[i] = sum_array[i - 1] + array_a[i];assert(1 <= array_a[i] && array_a[i] <= 1e7);}auto get_sum_from_a_to_b = [&](int left, int right) -> long long {return sum_array[right] - (left > 0 ? sum_array[left - 1] : 0);};std::deque<int> q;int ans = 0;int start = -1, end = -1;long long total_size = -1;for (int i = 1; i < n - 1; ++i) {if (array_a[i] > array_a[i - 1] && array_a[i] > array_a[i + 1]) {q.push_back(i);while (!q.empty() && get_sum_from_a_to_b(q.front() - 1, q.back() + 1) > k) {q.pop_front();}if (!q.empty()) {long long current_size = get_sum_from_a_to_b(q.front() - 1, q.back() + 1);if (q.size() > ans || (q.size() == ans && total_size > current_size)) {ans = q.size();start = q.front() - 1;end = q.back() + 1;total_size = current_size;}}}}assert(ans != 0);std::ostringstream oss;oss << ans << "," << start + 1 << "," << end + 1;return oss.str();
}int main() {std::cout << (solution(8, 15000, {1000, 3000, 2000, 4000, 3000, 2000, 4000, 2000}) == "2,1,5") << std::endl;std::cout << (solution(8, 15000, {2000, 5000, 2000, 1000, 4000, 2000, 4000, 3000}) == "2,4,8") << std::endl;std::cout << (solution(5, 10000, {3000, 4000, 1000, 5000, 2000}) == "1,1,3") << std::endl;std::cout << (solution(6, 8000, {1000, 2000, 3000, 4000, 500, 2500}) == "1,3,5") << std::endl;std::cout << (solution(10, 5000, {500, 1000, 1500, 500, 500, 1000, 1500, 500, 500, 1000}) == "1,2,4") << std::endl;return 0;
}

运行结果：