1、折木棍

题目描述：

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

输入描述
第一行是一个数 nn，表示开始时有多少根木棍 (1<=n<=3000)(1<=n<=3000) 第二行有 nn 个数，从第 11 个到第 nn 个分别表示从左到右的木棍长度。对任意木棍的长度 ll，有 1<=l<=30001<=l<=3000。

输出描述
输出一行，一个数，你最少所需的折断木棍的次数 xx

示例

输入:
5
3 5 13 9 12

输出:
1
说明
你可以将长度为 1313 的木棍折成长度分别为 55 和 88 的两根木棍，最终得到的排列是 3 5 5 8 9 12

思路:

从后往前遍历，建立一个单调栈，如果遇到比top大的，就想办法折出均匀的几段，这是在要比后一个小前一个大的情况，并且把折的最小的一个放栈里面

代码:

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;
}

2、打印出失序的线程ID

题目描述

输入一个正整数n.表示接下来有n行数字，每行一个数字（不重复，可能无序），表示线程id,输出未出现的失序的线程ID

n的大小是小于等于2的32次方

示例

例如1：

输入(输入的线程ID不一定有序)
5
2
3
4
5
6
输出：
1

例如2：

输入：
4
1
2
3
4
输出：
5

思路：

输入数组中，排序一个，然后从前往后遍历，找出空缺的位置。