# 贪心算法-分糖果问题

## 需求因子满足分法

```python
'''
已知一些孩子和一些糖果，每个孩子有需求因子g，每个糖果有大小s，当某个糖果的大小s >= 某个孩子的需求因子g时，代表该糖果可以满足该孩子;求使用这 些糖果，最多能满足多少孩子?
如：需求因子数组g = [5, 10, 2, 9, 15, 9]，糖果大小数组s = [6, 1, 20, 3, 8];最多可以 满足3个孩子。

思路：对需求因子、糖果数组，进行小到大排序
按照顺序使用各糖果尝试是否可满足某个孩子，每个糖果只尝试1次;
若尝试成功，则换下一个孩子尝试;直到发现没更多的孩子或者没更多的糖果，循环结束
'''

if __name__ == '__main__':
    g = [5, 10, 2, 9, 15, 9]
    s = [6, 1, 20, 3, 8]
    num = 0
    s_g = sorted(g)
    s_s = sorted(s)

    gi = 0
    si = 0
    while si < len(s) and gi < len(g):
        if s_s[si] >= s_g[gi]:
            num += 1
            si += 1
            gi += 1
        else:
            si += 1
    print(num)
```

## 优先级的分法

```python
'''
有n个人，每个人有一定的优先等级，等级高的人要比身边等级低得人得到的多，每个人都不会分不到(至少分1个)
'''

def split_candy(rank_list):
    length = len(rank_list)
    candy_list = [1] * length
    for i in range(length - 1):
        if rank_list[i] < rank_list[i + 1]:
            candy_list[i + 1] = candy_list[i] + 1
    for i in range(length - 1, 0, -1):
        if rank_list[i - 1] > rank_list[i] and candy_list[i - 1] <= candy_list[i]:
            candy_list[i - 1] += candy_list[i]

    print(sum(candy_list)) # 至少要拿这么多个糖出来才满足要求
    print('优先级为：', rank_list)
    print('分得的糖果为：', candy_list)


if __name__ == '__main__':
    print("试结果：")
    rank_list = [2, 3, 4, 8, 1, 5, 6]
    split_candy(rank_list)


'''
16
优先级为： [2, 3, 4, 8, 1, 5, 6]
分得的糖果为： [1, 2, 3, 4, 1, 2, 3]
'''
```


---

# 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://im-qianuxn.gitbook.io/pytorch/ji-suan-ji/shua-ti/si-xiang-lei/tan-xin/tan-xin-tang-guo-wen-ti.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.