建立一个个人网站,汕头建设信息网官网,专业建站推广服务,西安网站建设现状挑两个简单的写写
目录 一、蛋糕工厂产能规划
问题描述
输入格式
输出格式
解题思路#xff1a;
问题理解
数据结构选择
算法步骤
关键点
最终代码#xff1a;
运行结果#xff1a;编辑
二、优质章节的连续选择
问题描述
输入格式
输出格式
解题思路
问题理解
数据结构选择
算法步骤
关键点
最终代码
运行结果编辑
二、优质章节的连续选择
问题描述
输入格式
输出格式
解题思路
问题理解
数据结构选择
算法步骤
最终代码
运行结果 一、蛋糕工厂产能规划
问题描述
小明开了一家蛋糕工厂目前工厂里面有 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 个蛋糕。目标是计算出最少需要多少天才能完成生产计划。
数据结构选择
由于我们需要动态地调整机器和工人的数量并且需要计算每天的生产量和剩余蛋糕数因此我们可以使用一个循环来模拟每一天的生产过程。
算法步骤 初始化 初始机器数量 m初始工人数量 w每天的生产成本 p目标生产量 n当前天数 days当前剩余蛋糕数 cakes 循环模拟每一天 计算当天的生产量 production m * w更新剩余蛋糕数 cakes production检查是否已经达到目标生产量 n如果是则返回当前天数 days计算可以购买的机器和工人的最大数量 max_buy cakes / p尝试用剩余的蛋糕购买机器和工人使得 m * w 最大化更新机器和工人的数量增加一天 days 返回结果 当达到或超过目标生产量 n 时返回当前天数 days
关键点
在每次购买机器和工人时需要考虑如何分配购买的资源使得 m * w 最大化。需要动态调整机器和工人的数量以确保每天的生产量最大化。 最终代码
#include iostream
#include algorithm
#include limitsint solution(int m, int w, int p, int n) {int passes 0;long long candy 0; // 使用 long long 防止溢出long long run std::numeric_limitslong long::max();while (candy n) {if (m std::numeric_limitslong 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_limitslong long::max() / w) {candy std::numeric_limitslong long::max();} else {candy step * m * w;run std::min(run, static_castlong long(passes) ((n - candy m * w - 1) / (m * w)));}}}return std::min(passes, static_castint(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 和 k3≤n≤10^50≤k≤10^9
第二行是 n 个整数 a[i]1≤a[i]≤10^7
输出格式
输出整数 m、start、endm 表示优质章节的数量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^50≤k≤10^9
1≤a[i]≤10^7 解题思路
问题理解
目标从一本书的连续章节中挑选出总字数不超过 k 的章节使得优质章节比前后章节字数都多的章节的数量最多。约束 章节必须是连续的。总字数不超过 k。优质章节不能是挑选出来的第一个或最后一个章节。
数据结构选择
数组用于存储每个章节的字数。滑动窗口用于在数组中寻找满足条件的连续子数组。
算法步骤 初始化 使用两个指针 start 和 end 来表示当前窗口的开始和结束位置。使用变量 current_sum 来记录当前窗口的总字数。使用变量 best_start 和 best_end 来记录最优解的开始和结束位置。使用变量 best_quality_count 来记录最优解中的优质章节数量。 滑动窗口 从左到右遍历数组逐步扩展 end 指针直到总字数超过 k。当总字数超过 k 时移动 start 指针直到总字数再次小于等于 k。在每次移动 end 指针时检查当前窗口内的优质章节数量并更新最优解。 优质章节判断 对于每个窗口遍历其中的章节判断是否为优质章节比前后章节字数都多。注意第一个和最后一个章节不能作为优质章节。 结果输出 最终输出最优解的优质章节数量、开始位置和结束位置。
最终代码
#include bits/stdc.hstd::string solution(int n, int k, std::vectorint array_a) {assert(n array_a.size());assert(3 n n 1e5);assert(0 k k 1e9);std::vectorlong 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::dequeint 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;
}
运行结果
