【题解】最大配对
【题解】自动晾衣机
【题目描述】
有一个环形可以晾衣服的衣架，有若干个夹子组成，它可以晾不同长度的衣服（占用多个夹子），并且每两件衣服中间要有一个空夹子作为空位，下面需要依次晾干几件长度不一的衣服，请你给出某个夹子的使用情况。
【输入格式】
第一行一个数n，表示晾衣架的长度。(n<100000)
接下来有若干条数据，每条数据第一行若干个数（数据保证不会占满n），表示衣服的长度
第二行一个数 i，表示要查询 i 位置的使用情况
【输出格式】
输出第x位置夹子的状态
对于每个数据，输出一个状态占一行，其中使用0表示未使用，1表示有衣服，2表示格子用于隔开衣服。
【样例输入】
50 2 33 2 34 3 25 2 1 50
【样例输出】
2 0
【题解】金银岛
【题解】流感传染
【题目描述】
有一批易感人群住在网格状的宿舍区内，宿舍区为n\*n的矩阵，每个格点为一个房间，房间里可能住人，也可能空着。在第一天，有些房间里的人得了流感，以后每天，得流感的人会使其邻居传染上流感，（已经得病的不变），空房间不会传染。请输出第m天得流感的人数。
【输入描述】
第一行一个数字n，n不超过100，表示有n*n的宿舍房间。
接下来的n行，每行n个字符，’.’表示第一天该房间住着健康的人，’#’表示该房间空着，’@’表示第一天该房间住着得流感的人。
接下来的一行是一个整数m，m不超过100。
【输出描述】
输出第m天，得流感的人数。
【样例输入】
5 ....# .#.@. .#@.. #.... ..... 4
【样例输出】
16
数列分段
题目描述
对于给定的一个长度为N的正整数数列A[i]，现要将其分成连续的若干段，并且每段和不超过M（可以等于M），问最少能将其分成多少段使得满足要求。
输入格式
第1行包含两个正整数N，M，表示了数列A[i]的长度与每段和的最大值；
第2行包含N个空格隔开的非负整数A[i]，如题目所述。
输出格式
一个正整数，输出最少划分的段数。
样例输入
5 6 4 2 4 5 1
样例输出
3
提示
【数据范围】
对于20%的数据，有N≤10；
对于40%的数据，有N≤1000；
对于100%的数据，有N≤100000，M≤109，M大于所有数的最小值，A[i]之和不超过109。
线段
题目描述
在一个数轴上有n条线段，现选取其中k条线段使得这k条线段两两没有重合部分，问最大的k为多少?
输入格式
第一行为一个正整数n，下面n行每行2个数字ai，bi，描述每条线段。
输出格式
输出文件仅包括1个整数，为k的最大值。
样例输入
3 0 2 2 4 1 3
样例输出
2
提示
【数据规模】
对于20%的数据，n≤10。
对于50%的数据，n≤1000。
对于70%的数据，n≤100000。
对于20%的数据，n≤1000000,0≤ai<bi≤1000000。
糖果传递
题目描述
有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。
输入格式
第一行一个正整数n≤1000000，表示小朋友的个数．
接下来n行，每行一个整数ai，表示第i个小朋友得到的糖果的颗数．
输出格式
求使所有人获得均等糖果的最小代价。
样例输入
4 1 2 5 4
样例输出
4
家庭作业
【算法】单调栈
一、单调栈
单调栈（Monotonic Stack）是一种特殊的栈结构，其核心思想是维护栈内元素的单调性（单调递增或单调递减）。单调栈通常用于解决与元素大小关系相关的问题，例如：
找到数组中每个元素的下一个更大（或更小）元素。
计算数组中每个元素左边或右边的第一个更大（或更小）元素。
解决与区间最值相关的问题（如最大矩形面积）。
二、特点
单调性：栈内元素始终保持单调递增或单调递减。
操作规则：
如果新元素满足单调性，直接压入栈。
时间复杂度：由于每个元素最多入栈和出栈一次，因此时间复杂度通常为O(n)
如果新元素破坏了单调性，则弹出栈顶元素，直到满足单调性为止。
三、应用场景
下一个更大元素：
给定一个数组，找到每个元素的下一个更大元素。每日温度：
给定一个温度数组，计算每天需要等待多少天才能遇到更高的温度。最大矩形面积：
给定一个柱状图，计算其中最大的矩形面积。滑动窗口最大值：
在滑动窗口中快速找到最大值。
四、步骤
以找到数组中每个元素的下一个更大元素为例：
初始化：创建一个空栈和一个结果数组。
遍历数组：
如果当前元素大于栈顶元素，则栈顶元素的下一个更大元素就是当前元素。
弹出栈顶元素，并更新结果数组。
重复上述过程，直到当前元素小于等于栈顶元素或栈为空。
将当前元素压入栈。
处理剩余元素：遍历结束后，栈中剩余的元素没有下一个更大元素，将其结果设置为
-1。