資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++程式：找出消滅所有怪物所需的最少炸彈數量
假設我們有兩個陣列X和H。兩者都有N個元素，還有另外兩個數字D和A。在一個故事中，一隻銀狐正在與N個怪物戰鬥。怪物們排成一列，第i個怪物的座標是X[i]，其生命值是H[i]。銀狐可以使用炸彈攻擊怪物。在x位置投下炸彈將對x - D到x + D範圍內的所有怪物造成傷害。它們的生命值將減少A。當所有怪物的生命值都降為0時，狐狸獲勝。我們必須找到獲勝所需的最小炸彈數量。
因此，如果輸入類似於D = 3；A = 2；X = [1, 5, 9]；H = [2, 4, 2]，則輸出為2，因為第一個炸彈在座標4處，新的生命值是[0, 2, 2]，然後在位置6處使所有生命值都為[0, 0, 0]。
步驟
為了解決這個問題，我們將遵循以下步驟：
Define a large array q Define an array of x and h pairs n := size of X d := D a := A for initialize i := 1, when i <= n, update (increase i by 1), do: num[i].x := X[i - 1] num[i].h := H[i - 1] sort the array num sum := 0 for initialize i := 1, when i <= n, update (increase i by 1), do: q[i] := q[i] + q[i - 1] num[i].h := num[i].h - q[i] * a if num[i].h <= 0, then: Ignore following part, skip to the next iteration p := (if num[i].h mod a is same as 0, then num[i].h / a, otherwise num[i].h / a + 1) tmp := num[i].x + 2 * d sum := sum + p q[i] := q[i] + p l := i, r = n while l < r, do: mid := (l + r + 1) / 2 if num[mid].x <= tmp, then: l := mid Otherwise r := mid - 1 q[l + 1] - = p return sum
示例
讓我們來看下面的實現，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 20;
int n;
int d, a, q[maxn];
struct node{
int x, h;
bool operator<(const node& a) const{
return x < a.x;
}
} num[maxn];
int solve(int D, int A, vector<int> X, vector<int> H){
n = X.size();
d = D;
a = A;
for (int i = 1; i <= n; i++){
num[i].x = X[i - 1];
num[i].h = H[i - 1];
}
sort(num + 1, num + n + 1);
int sum = 0;
for (int i = 1; i <= n; i++){
q[i] += q[i - 1];
num[i].h -= q[i] * a;
if (num[i].h <= 0)
continue;
int p = (num[i].h % a == 0 ? num[i].h / a : num[i].h / a + 1);
int tmp = num[i].x + 2 * d;
sum += p;
q[i] += p;
int l = i, r = n;
while (l < r){
int mid = (l + r + 1) >> 1;
if (num[mid].x <= tmp)
l = mid;
else
r = mid - 1;
}
q[l + 1] -= p;
}
return sum;
}
int main(){
int D = 3;
int A = 2;
vector<int> X = { 1, 5, 9 };
vector<int> H = { 2, 4, 2 };
cout << solve(D, A, X, H) << endl;
}輸入
3, 2, { 1, 5, 9 }, { 2, 4, 2 }輸出
2
更新於：2022年3月2日
234 次瀏覽
廣告