# 面试题 16.11

You are building a diving board by placing a bunch of planks of wood end-to-end. There are two types of planks, one of length shorter and one of length longer. You must use exactly K planks of wood. Write a method to generate all possible lengths for the diving board.

return all lengths in non-decreasing order.

Example:

Input: shorter = 1 longer = 2 k = 3 Output: {3,4,5,6} Note:

0 < shorter <= longer 0 <= k <= 100000

## Solutions

1. **hashset O(k)**

```cpp
class Solution {
public:
    vector<int> divingBoard(int shorter, int longer, int k) {
        if (k <= 0) return {};
        unordered_set<int> seen;
        for (int i = 0; i <= k; i++) {
            seen.insert(shorter * i + longer * (k - i));
        }
        vector<int> lens(seen.begin(), seen.end());
        sort(lens.begin(), lens.end());

        return lens;
    }
};
```

1. **math O(k)**
2. reference: <https://leetcode-cn.com/problems/diving-board-lcci/solution/qing-xi-yi-dong-de-shu-xue-tui-dao-che-di-nong-don/>
3. The key point is: length of all possible combinations of `(shorter * i + longer * (k - i))` are different than each other. Thus the hashset can be omitted.
   * This is true only when `shorter != longer`, otherwise their is only one answer.&#x20;
   * Proof:

```
len = f(i) = shorter * i + longer * (k - i)
           = shorter * i - longer * i + longer * k
           = (shorter - longer) * i + longer * k

As this is a monotonically decreasing function, `f(i)` is unique for each different i.
```

```cpp
class Solution {
public:
    vector<int> divingBoard(int shorter, int longer, int k) {
        if (k <= 0) return {};
        if (shorter == longer)
            return {shorter * k};

        vector<int> lens;
        for (int i = 0; i <= k; i++)
            lens.push_back(longer * i + shorter * (k - i));

        return lens;
    }
};
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://zhongquan789.gitbook.io/leetcode/lcci/mian-shi-ti-16.11.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.