目錄
1921. 消滅怪物的最大數(shù)量
題目描述：
實現(xiàn)代碼與解析：
貪心
原理思路：
1921. 消滅怪物的最大數(shù)量
題目描述：
????????你正在玩一款電子游戲，在游戲中你需要保護城市免受怪物侵襲。給你一個?下標(biāo)從 0 開始?且長度為?n?的整數(shù)數(shù)組?dist?，其中?dist[i]?是第?i?個怪物與城市的?初始距離（單位：米）。
怪物以?恒定?的速度走向城市。給你一個長度為?n?的整數(shù)數(shù)組?speed?表示每個怪物的速度，其中?speed[i]?是第?i?個怪物的速度（單位：米/分）。
怪物從?第 0 分鐘?時開始移動。你有一把武器，并可以?選擇?在每一分鐘的開始時使用，包括第 0 分鐘。但是你無法在一分鐘的中間使用武器。這種武器威力驚人，一次可以消滅任一還活著的怪物。
一旦任一怪物到達(dá)城市，你就輸?shù)袅诉@場游戲。如果某個怪物?恰?在某一分鐘開始時到達(dá)城市，這會被視為?輸?shù)?/strong>?游戲，在你可以使用武器之前，游戲就會結(jié)束。
返回在你輸?shù)粲螒蚯翱梢韵麥绲墓治锏?最大?數(shù)量。如果你可以在所有怪物到達(dá)城市前將它們?nèi)肯麥纾祷??n?。
示例 1：
輸入：dist = [1,3,4], speed = [1,1,1] 輸出：3 解釋： 第 0 分鐘開始時，怪物的距離是 [1,3,4]，你消滅了第一個怪物。 第 1 分鐘開始時，怪物的距離是 [X,2,3]，你沒有消滅任何怪物。 第 2 分鐘開始時，怪物的距離是 [X,1,2]，你消滅了第二個怪物。 第 3 分鐘開始時，怪物的距離是 [X,X,1]，你消滅了第三個怪物。 所有 3 個怪物都可以被消滅。
示例 2：
輸入：dist = [1,1,2,3], speed = [1,1,1,1] 輸出：1 解釋： 第 0 分鐘開始時，怪物的距離是 [1,1,2,3]，你消滅了第一個怪物。 第 1 分鐘開始時，怪物的距離是 [X,0,1,2]，你輸?shù)袅擞螒颉?你只能消滅 1 個怪物。
示例 3：文章來源：http://www.zghlxwxcb.cn/news/detail-693985.html
輸入：dist = [3,2,4], speed = [5,3,2] 輸出：1 解釋： 第 0 分鐘開始時，怪物的距離是 [3,2,4]，你消滅了第一個怪物。 第 1 分鐘開始時，怪物的距離是 [X,0,2]，你輸?shù)袅擞螒颉? 你只能消滅 1 個怪物。
實現(xiàn)代碼與解析：
貪心
class Solution {
public:
int eliminateMaximum(vector<int>& dist, vector<int>& speed) {
int n = dist.size();
vector<int> times(n, 0);
for (int i = 0; i < n; i++) // 到達(dá)時間
times[i] = (dist[i] - 1) / speed[i]; // 向下取整
sort(times.begin(), times.end());
for (int i = 0; i < n; i++)
if (times[i] < i) return i; // 到達(dá)時間小于開槍時間
return n;
}
};原理思路：
? ? ? ? 簡單題，看代碼就行。文章來源地址http://www.zghlxwxcb.cn/news/detail-693985.html
到了這里，關(guān)于LeetCode每日一題：1921. 消滅怪物的最大數(shù)量（2023.9.3 C++）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
