挑兩個簡單的寫寫

目錄

一、蛋糕工廠產能規(guī)劃

問題描述

輸入格式

輸出格式

解題思路：?

問題理解

數(shù)據(jù)結構選擇

算法步驟

關鍵點

最終代碼：

運行結果：?編輯?

二、優(yōu)質章節(jié)的連續(xù)選擇?

問題描述

輸入格式

輸出格式

解題思路：

問題理解

數(shù)據(jù)結構選擇

算法步驟

最終代碼：

運行結果：?

?

?

?

---

一、蛋糕工廠產能規(guī)劃

問題描述

小明開了一家蛋糕工廠，目前工廠里面有 m 臺機器和 w 個工人，每天可以生產的蛋糕數(shù)量是 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 所以在第四天就完成了生產計劃

輸入格式

輸入的數(shù)據(jù)只有一行，空格分割的四個整數(shù)，代表 m, w, p, n

數(shù)據(jù)約束

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

輸出格式

輸出一個整數(shù)用來表示需要幾天才能完成生產計劃

輸入樣例

3 1 2 12

輸出樣例

3

樣例解釋

• 第一天：生產的蛋糕數(shù)量 m * w = 3 * 1 = 3。此時花 2 個蛋糕，雇傭了另外一個工人，此時 w = 2，依然剩余 1 個蛋糕

• 第二天：生產的蛋糕數(shù)量 3 * 2 = 6。此時花 2 * p = 4 個蛋糕雇傭了另外一個工人，同時新增了另外一臺機器，此時 m = 4, w = 3，而且剩余 3 個蛋糕（包括第一天剩余的那一個）

• 第三天：生產的蛋糕數(shù)量 4 * 3 = 12，已經(jīng)符合預期的產量了，所以只需要三天就可以完成生產計劃

解題思路：?

問題理解

小明的蛋糕工廠每天可以生產?m * w?個蛋糕。為了盡快完成生產?n?個蛋糕的任務，他可以選擇用蛋糕購買額外的機器或工人，每臺機器或每個工人需要花費?p?個蛋糕。目標是計算出最少需要多少天才能完成生產計劃。

數(shù)據(jù)結構選擇

由于我們需要動態(tài)地調整機器和工人的數(shù)量，并且需要計算每天的生產量和剩余蛋糕數(shù)，因此我們可以使用一個循環(huán)來模擬每一天的生產過程。

算法步驟

1. 初始化：

   • 初始機器數(shù)量?m
   • 初始工人數(shù)量?w
   • 每天的生產成本?p
   • 目標生產量?n
   • 當前天數(shù)?days
   • 當前剩余蛋糕數(shù)?cakes

2. 循環(huán)模擬每一天：

   • 計算當天的生產量?production = m * w
   • 更新剩余蛋糕數(shù)?cakes += production
   • 檢查是否已經(jīng)達到目標生產量?n，如果是，則返回當前天數(shù)?days
   • 計算可以購買的機器和工人的最大數(shù)量?max_buy = cakes / p
   • 嘗試用剩余的蛋糕購買機器和工人，使得?m * w?最大化
   • 更新機器和工人的數(shù)量
   • 增加一天?days++

3. 返回結果：

   • 當達到或超過目標生產量?n?時，返回當前天數(shù)?days

關鍵點

• 在每次購買機器和工人時，需要考慮如何分配購買的資源，使得?m * w?最大化。
• 需要動態(tài)調整機器和工人的數(shù)量，以確保每天的生產量最大化。

?

最終代碼：

#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;
}

運行結果：?

二、優(yōu)質章節(jié)的連續(xù)選擇?

問題描述

番茄小說上有很多精彩的書籍，編輯想從其中一本書籍中挑選出若干精彩章節(jié)。這本書有 n 個章節(jié)，每個章節(jié)的文字數(shù)量分別為 a[i]（1≤i≤n）。

出于閱讀體驗的考慮，編輯希望挑選出來的章節(jié)是在書中是連續(xù)的，并且總字數(shù)不超過 k。

編輯是特別的書蟲，他認為在挑選出來的章節(jié)中，如果某個章節(jié)的文字數(shù)量比前后章節(jié)都多，則這個章節(jié)是優(yōu)質章節(jié)。挑選出來章節(jié)中的第一章和最后一章不能作為優(yōu)質章節(jié)。

編輯想知道，如何挑選才能產生盡可能多的優(yōu)質章節(jié)，并且滿足總字數(shù)不超過 k。

輸入格式

第一行是整數(shù) n 和 k；（3≤n≤10^5，0≤k≤10^9）

第二行是 n 個整數(shù) a[i]；（1≤a[i]≤10^7）

輸出格式

輸出整數(shù) m、start、end，m 表示優(yōu)質章節(jié)的數(shù)量，start 表示挑選出來的首個章節(jié)在書中的位置，end 是挑出來的末尾章節(jié)在書中的位置；

如果優(yōu)質章節(jié)數(shù)量相同的選擇有多個，則輸出總字數(shù)最少的選擇；如果仍有多個，則輸出 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 個優(yōu)質章節(jié)，分別是第 2 章和第 4 章；

樣例 2，選擇第 4 章到第 8 章，一共有 2 個優(yōu)質章節(jié)，分別是第 5 章和第 7 章；

數(shù)據(jù)范圍

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

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

?

解題思路：

問題理解

1. 目標：從一本書的連續(xù)章節(jié)中挑選出總字數(shù)不超過?k?的章節(jié)，使得優(yōu)質章節(jié)（比前后章節(jié)字數(shù)都多的章節(jié)）的數(shù)量最多。
2. 約束：
   • 章節(jié)必須是連續(xù)的。
   • 總字數(shù)不超過?k。
   • 優(yōu)質章節(jié)不能是挑選出來的第一個或最后一個章節(jié)。

數(shù)據(jù)結構選擇

• 數(shù)組：用于存儲每個章節(jié)的字數(shù)。
• 滑動窗口：用于在數(shù)組中尋找滿足條件的連續(xù)子數(shù)組。

算法步驟

1. 初始化：

   • 使用兩個指針?start?和?end?來表示當前窗口的開始和結束位置。
   • 使用變量?current_sum?來記錄當前窗口的總字數(shù)。
   • 使用變量?best_start?和?best_end?來記錄最優(yōu)解的開始和結束位置。
   • 使用變量?best_quality_count?來記錄最優(yōu)解中的優(yōu)質章節(jié)數(shù)量。

2. 滑動窗口：

   • 從左到右遍歷數(shù)組，逐步擴展?end?指針，直到總字數(shù)超過?k。
   • 當總字數(shù)超過?k?時，移動?start?指針，直到總字數(shù)再次小于等于?k。
   • 在每次移動?end?指針時，檢查當前窗口內的優(yōu)質章節(jié)數(shù)量，并更新最優(yōu)解。

3. 優(yōu)質章節(jié)判斷：

   • 對于每個窗口，遍歷其中的章節(jié)，判斷是否為優(yōu)質章節(jié)（比前后章節(jié)字數(shù)都多）。
   • 注意：第一個和最后一個章節(jié)不能作為優(yōu)質章節(jié)。

4. 結果輸出：

   • 最終輸出最優(yōu)解的優(yōu)質章節(jié)數(shù)量、開始位置和結束位置。

最終代碼：

#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;
}

運行結果：?

?

?

?