讨论/面试考题/头条笔试题-折木棍/
头条笔试题-折木棍

在你的面前从左到右摆放着n根长短不一的木棍,你每次可以折断一根木棍,并将折断后得到的两根木棍一左一右放在原来的位置(即若原木棍有左邻居,则两根新木棍必须放在左邻居的右边,若原木棍有右邻居,新木棍必须放在右邻居的左边,所有木棍保持左右排列)。折断后的两根木棍的长度必须为整数,且它们之和等于折断前的木棍长度。你希望最终从左到右的木棍长度单调不减,那么你需要折断多少次呢?

输入描述:
第一行是一个数n,表示开始时有多少根木棍(1<=n<=3000)第二行有n个数,从第1个到第n个分别表示从左到右的木棍长度。对任意木棍的长度l,有1<=l<=3000。
输出描述
输出一行,一个数,你最少所需的折断木棍的次数x

  1. 示例1
    输入:
5
3 5 13 9 12

输出

1

说明
你可以将长度为13的木棍折成长度分别为5和8的两根木棍,最终得到的排列是3 5 5 8 9 12

展开讨论
JasonRD发起于 2020-03-25

折木棍

题目描述

在你的面前从左到右摆放着n根长短不一的木棍,你每次可以折断一根木棍,并将折断后得到的两根木棍一左一右放在原来的位置(即若原木棍有左邻居,则两根新木棍必须放在左邻居的右边,若原木棍有右邻居,新木棍必须放在右邻居的左边,所有木棍保持左右排列)。折断后的两根木棍的长度必须为整数,且它们之和等于折断前的木棍长度。你希望最终从左到右的木棍长度单调不减,那么你需要折断多少次呢?

用例

输入:[3,5,13,9,12]
输出:1

输入:[3,12,13,9,12]
输出:2

输入:[3,13,12,9,12]
输出:3

输入:[3,13,60,7]
输出:10

输入:[3,63,7]
输出:8

输入:[9,1]
输出:8

思路

  1. 从后往前遍历,使用单调递减栈
  2. 在原本应该出栈的时机,将那根木棒折断成若干小于等于栈顶的小木棒
  3. 并让他们尽量保持平均大小,将略小一的入栈

图解

图片.png

答题

int breakNum(vector<int>& nums)
{
    int ans = 0;
    stack<int> st;
    for (int i = nums.size() - 1; i >= 0; i--)
    {
        if (!st.empty() && st.top() < nums[i])
        {
            int t = (nums[i] - 1) / st.top();
            ans += t;
            st.push(nums[i] / (t + 1));
            continue;
        }
        st.push(nums[i]);
    }
    return ans;
}

优化一下只用单调栈的思想

int breakNum(vector<int>& nums)
{
    int ans = 0;
    for (int i = nums.size() - 2; i >= 0; i--)
    {
        if (nums[i + 1] >= nums[i]) continue;
        int t = (nums[i] - 1) / nums[i + 1];
        ans += t;
        nums[i] /= (t + 1);
    }
    return ans;
}

致谢

感谢您的观看,希望对您有帮助,欢迎热烈的交流!

如果感觉还不错就点个赞吧~

这是 我的leetcode ,帮助我收集整理题目,可以方便的 visual studio 调试,欢迎关注,star

19
展开全部 2 讨论