leetcode-300 最优除法

553. 最优除法 - 力扣（LeetCode） (leetcode-cn.com)

题目

给定一组正整数，相邻的整数之间将会进行浮点除法操作。例如， [2,3,4] -> 2 / 3 / 4 。

但是，你可以在任意位置添加任意数目的括号，来改变算数的优先级。你需要找出怎么添加括号，才能得到最大的结果，并且返回相应的字符串格式的表达式。你的表达式不应该含有冗余的括号。

题意

给定一个数组，数组之间的数会依次构成一个除法表达式，可以在任意位置添加括号改变算数优先级，求入会添加括号使得除法表达式的值最大。

思路

数学题

对于一个除法$\frac{x}{y}$，需要使得表达式值最大，那么就需要使得x的值最大，y的值最小。

根据题目可得，nums[1]肯定是在分母上，因此分母最小值为单独的nums[1]。此时只需要将其余所有数都通过添加括号调整到分子上，可使得算法表达式的值最大。

因此只需要通过括号将第二个数到最后一个数包含即可，即：nums[0]/(nums[1]/nums[2]/nums[3]…);

代码

/*
 *@File Name          :leetcode-553.cpp
 *@Author             :cc
 *@Version            :1.0.0
 *@Date               :2022/2/27 9:06
 *@Description        :
 *@Function List      :
 *@History            :
 */

#include "algorithm"
#include "string"
#include "vector"
using namespace std;

class Solution {
public:
    string optimalDivision(vector<int>& nums) {
        string ans= to_string(nums[0]);
        for(int i = 1; i < nums.size(); i++){
            if(nums.size()>2 && i == 1)
                ans += "/(";
            else ans += "/";
            ans += to_string(nums[i]);
            if(nums.size()>2 && i == nums.size()-1)
                ans += ")";
        }return ans;
    }
};