Cho mảng số nguyên dương, thực hiện phép chia liên tiếp a/b/c/.... Có thể thêm ngoặc để thay đổi thứ tự ưu tiên. Tìm biểu thức cho kết quả lớn nhất (không ngoặc dư thừa).
Ví dụ: [1000,100,10,2] → "1000/(100/10/2)".
Quan sát
Để kết quả lớn nhất, tử số cố định là phần tử đầu, mẫu số nên nhỏ nhất → nhóm tất cả phần tử còn lại vào mẫu số với ngoặc đơn: a/(b/c/d/...).
Mã nguồn C++
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string optimalDivision(vector<int>& nums) {
int n = nums.size();
if (n == 0) return "";
string num = to_string(nums[0]);
if (n == 1) return num;
if (n == 2) return num + "/" + to_string(nums[1]);
string den = "";
for (int i = 1; i < n; i++) {
den += to_string(nums[i]);
if (i != n-1) den += "/";
}
return num + "/(" + den + ")";
}
};
int main() {
vector<int> v = {1000,100,10,2};
Solution ob;
cout << ob.optimalDivision(v);
return 0;
}
Đầu vào / Đầu ra
Input: [1000,100,10,2]
Output: 1000/(100/10/2)