挑兩個(gè)簡(jiǎn)單的寫(xiě)寫(xiě)

目錄

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

問(wèn)題描述

輸入格式

輸出格式

解題思路：?

問(wèn)題理解

數(shù)據(jù)結(jié)構(gòu)選擇

算法步驟

關(guān)鍵點(diǎn)

最終代碼：

運(yùn)行結(jié)果：?編輯?

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

問(wèn)題描述

輸入格式

輸出格式

解題思路：

問(wèn)題理解

數(shù)據(jù)結(jié)構(gòu)選擇

算法步驟

最終代碼：

運(yùn)行結(jié)果：?

?

?

?

---

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

問(wèn)題描述

小明開(kāi)了一家蛋糕工廠，目前工廠里面有 m 臺(tái)機(jī)器和 w 個(gè)工人，每天可以生產(chǎn)的蛋糕數(shù)量是 m * w。有一天他接到了一個(gè)訂單，需要生產(chǎn) n 個(gè)蛋糕，客戶(hù)希望能夠盡快的一次性交付，但是他算不清楚需要多少天才能生產(chǎn)完，請(qǐng)你幫幫小明。（提示：為了提升產(chǎn)能，每天可以用蛋糕購(gòu)買(mǎi)額外的機(jī)器或者工人，每臺(tái)機(jī)器或者每個(gè)工人，需要花費(fèi) p 個(gè)蛋糕。）

為了方便理解，我們舉個(gè)例子：假如最開(kāi)始小明的工廠只有 m = 1 臺(tái)機(jī)器和 w = 2 個(gè)工人，每次擴(kuò)大產(chǎn)能需要的花費(fèi)是 p = 1，為了生產(chǎn) n = 60 個(gè)蛋糕，可以這么操作：

• 第一天：m * w = 1 * 2 = 2 生產(chǎn) 2 個(gè)蛋糕，同時(shí)新增 2 臺(tái)機(jī)器，此時(shí) m = 3，剩余蛋糕 0

• 第二天：m * w = 3 * 2 = 6 生產(chǎn) 6 個(gè)蛋糕，同時(shí)新增 3 臺(tái)機(jī)器，3 個(gè)工人，此時(shí) m = 6, w = 5，剩余蛋糕 0

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

• 第四天：m * w = 6 * 5 = 30 所以在第四天就完成了生產(chǎn)計(jì)劃

輸入格式

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

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

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

輸出格式

輸出一個(gè)整數(shù)用來(lái)表示需要幾天才能完成生產(chǎn)計(jì)劃

輸入樣例

3 1 2 12

輸出樣例

3

樣例解釋

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

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

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

解題思路：?

問(wèn)題理解

小明的蛋糕工廠每天可以生產(chǎn)?m * w?個(gè)蛋糕。為了盡快完成生產(chǎn)?n?個(gè)蛋糕的任務(wù)，他可以選擇用蛋糕購(gòu)買(mǎi)額外的機(jī)器或工人，每臺(tái)機(jī)器或每個(gè)工人需要花費(fèi)?p?個(gè)蛋糕。目標(biāo)是計(jì)算出最少需要多少天才能完成生產(chǎn)計(jì)劃。

數(shù)據(jù)結(jié)構(gòu)選擇

由于我們需要?jiǎng)討B(tài)地調(diào)整機(jī)器和工人的數(shù)量，并且需要計(jì)算每天的生產(chǎn)量和剩余蛋糕數(shù)，因此我們可以使用一個(gè)循環(huán)來(lái)模擬每一天的生產(chǎn)過(guò)程。

算法步驟

1. 初始化：

   • 初始機(jī)器數(shù)量?m
   • 初始工人數(shù)量?w
   • 每天的生產(chǎn)成本?p
   • 目標(biāo)生產(chǎn)量?n
   • 當(dāng)前天數(shù)?days
   • 當(dāng)前剩余蛋糕數(shù)?cakes

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

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

3. 返回結(jié)果：

   • 當(dāng)達(dá)到或超過(guò)目標(biāo)生產(chǎn)量?n?時(shí)，返回當(dāng)前天數(shù)?days

關(guān)鍵點(diǎn)

• 在每次購(gòu)買(mǎi)機(jī)器和工人時(shí)，需要考慮如何分配購(gòu)買(mǎi)的資源，使得?m * w?最大化。
• 需要?jiǎng)討B(tài)調(diào)整機(jī)器和工人的數(shù)量，以確保每天的生產(chǎn)量最大化。

?

最終代碼：

#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ùn)行結(jié)果：?

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

問(wèn)題描述

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

出于閱讀體驗(yàn)的考慮，編輯希望挑選出來(lái)的章節(jié)是在書(shū)中是連續(xù)的，并且總字?jǐn)?shù)不超過(guò) k。

編輯是特別的書(shū)蟲(chóng)，他認(rèn)為在挑選出來(lái)的章節(jié)中，如果某個(gè)章節(jié)的文字?jǐn)?shù)量比前后章節(jié)都多，則這個(gè)章節(jié)是優(yōu)質(zhì)章節(jié)。挑選出來(lái)章節(jié)中的第一章和最后一章不能作為優(yōu)質(zhì)章節(jié)。

編輯想知道，如何挑選才能產(chǎn)生盡可能多的優(yōu)質(zhì)章節(jié)，并且滿(mǎn)足總字?jǐn)?shù)不超過(guò) k。

輸入格式

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

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

輸出格式

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

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

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

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

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

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

?

解題思路：

問(wèn)題理解

1. 目標(biāo)：從一本書(shū)的連續(xù)章節(jié)中挑選出總字?jǐn)?shù)不超過(guò)?k?的章節(jié)，使得優(yōu)質(zhì)章節(jié)（比前后章節(jié)字?jǐn)?shù)都多的章節(jié)）的數(shù)量最多。
2. 約束：
   • 章節(jié)必須是連續(xù)的。
   • 總字?jǐn)?shù)不超過(guò)?k。
   • 優(yōu)質(zhì)章節(jié)不能是挑選出來(lái)的第一個(gè)或最后一個(gè)章節(jié)。

數(shù)據(jù)結(jié)構(gòu)選擇

• 數(shù)組：用于存儲(chǔ)每個(gè)章節(jié)的字?jǐn)?shù)。
• 滑動(dòng)窗口：用于在數(shù)組中尋找滿(mǎn)足條件的連續(xù)子數(shù)組。

算法步驟

1. 初始化：

   • 使用兩個(gè)指針?start?和?end?來(lái)表示當(dāng)前窗口的開(kāi)始和結(jié)束位置。
   • 使用變量?current_sum?來(lái)記錄當(dāng)前窗口的總字?jǐn)?shù)。
   • 使用變量?best_start?和?best_end?來(lái)記錄最優(yōu)解的開(kāi)始和結(jié)束位置。
   • 使用變量?best_quality_count?來(lái)記錄最優(yōu)解中的優(yōu)質(zhì)章節(jié)數(shù)量。

2. 滑動(dòng)窗口：

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

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

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

4. 結(jié)果輸出：

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

最終代碼：

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

運(yùn)行結(jié)果：?

?

?

?