公平，到底是什么？平均分，到底，算不算公平……



亚里士多德也曾经说过「公平并非简单的平等，而是根据每个人的贡献和才能来分配。」

今天，就以这句话为轴心，来论述一下吧。

> 公平并非简单的平等，而是根据每个人的贡献和才能来分配。

这句话，或许我们还可以讲其扩大化。就是所谓的平等，就是所有的人，都经过一个相等的衡量标准，来分配——而并非平均分配。

先举一个平均分配的反例吧。中国近代史中的 太平天国起义 大家都非常的熟悉。太平天国的「天朝田亩制度」，就是一个完全平均分配的象征——不论你耕种多少，都和那些好吃懒做的人分配到的一样，你说，这样公平吗？所以，从这个角度来说，即是这场起义成功了，也必定会因为这个制度而衰败。

再比如中国古代的封建制度，皇位的继承并非一味的平均分配，而是嫡长子继承制度来决定。这个规定看似可以视为——每个人都用一个相同的规则，是否为嫡长子而当皇帝。然而，这是大大不对的。上文论述的「衡量标准」，应该是一个非先天的，可以通过后天努力，人人可以到达的标准。

当然反例还有很多的，例如古希腊的民主政策，实际上每个人的投票权重是不一样的，诸如此类的内容，就不叙述了。

举了这么多反例，我们再看一个正向的例子，高考制度——并不是每个人都可以上清华。这看似非常的不合理，为什么清华的名额不拼均分配，每个人都可以上清华呢？但是细细想来，又非常的合理——你的成绩没有我好啊。所以，这个成绩，就是每一个人想等的衡量标准，而这样，也就实现了每个人的公平。

在来找一个比较专业的领域：

同样，在经济领域中，公平也不是简单的平均分配。在自由市场中，资源的分配是依据供求关系和价值进行的，这并非是平均分配。但是，这种分配方式能够有效地激励个体发挥创造力和竞争力，促进经济的发展。

总结来说，公平并非简单的平均分，而是其在固定衡量标准下的表现来分配的。

---

所以，当和妹妹吃饭的时候，为什么要和妹妹分配的一样多的？

我和她相差6岁，胃不一样，分配到的吃的就是应该不一样的呀，为什么要追求一味的和平，而不按照胃的大小这一衡量标准来分配呢？

当然，开个玩笑了……

公平，到底是什么

其实说是深交，但是起初并不是这样的。

刚开始就是英语老师自掏腰包，旨在让老外教我们提高英语——可是到最后，却本末倒次，Q&A 倒成了那节课的主要内容。



# 起因
这一切的刚开始，本来是非常的简单的——在周四的英语课结束的时候，老师告诉我们他自掏腰包，请了两个外教来给我们 如何学好英语 的讲座。

先不说自掏腰包是否属实的问题，我那个时候倒是 灵光一扎 ，想着这样的事情要给对方留下一个非常好的印象，于是想明天外教来的时候在黑板上画一个中国国旗🇨🇳，一个俄罗斯国旗🇷🇺和一个那个南美洲的外教的国籍的国旗。

想法💡一出来，可就是拦不住的了。我先找到了我们班的另外一位班长来商量这件事，确定这件事不是很离谱过后就准备去问老师。

一来，英语老师的办公室比较远，而且也毕竟要动用班级的东西——所以我们先请示了一下班主任。结果，班主任说应该上报学校和一些别的，反正这件事情就不了了之了。

当初我还以为因为我的行为第二天就听不到讲座了呢，吓我一跳。

# 等待
第二天上学的时候，一直在等待上午第四节课的英语课。

话说我还把第一节课错看成了英语。

好不容易等到了第四节课，结果老师说老外晚辅课的时候第二节来。

说实话，等待的过程属实不是特别好受。有一个好办法，就是干别的事情忘掉他。

# 偶遇

下午第一节是音乐课，下午第二节是物理课。

音乐课在行政楼上——而我们的教室在中楼——所以，我们英语课下课过后，就要从报告厅、作品展览区横穿而过。

这些外教肯定来学校也是需要参观一下的——于是，正巧他们也在这里。

女生们争着拍照，男生们却先保持观望态度——我们本来都以为是一个大胡子的，没有想到是两个干练的女将。

不过，这并不会造成更大的隔阂——最后，我们也和她们一起拍了照。

# 讲座
说实话，听讲座是一种享受——听英语的享受，但并不能听懂。

实话实说，她说的我只听懂了三四句——不光是我，大家都是这样的。问问题的时候我们甚至都不知道问题是什么意思。

老外还是会说中文的——但是和我们想象的不太一样，首先，会说的并不是很多——例如「窗户」就不会说。而且，我以前以为老外说话都是一个音调，实际上不是这样的——还不如一个音调呢，这个说话的方式就是猛的下降上升，听懂而已。

不过，总的来说，还是比较愉快的，听这样纯真的英语本来就是一种享受。不然，我们班的门口和窗户上为什么爬着隔壁两个班一百多个人的脸呢？

# Q&A

到快下课的时候，同学们才开始活跃起来，意识到再不问问题就没有机会了——几乎有一半以上的人举了手，两个外教忙的不亦说乎。下课过后就更加乱了，大家围着两个老师要签名。

不过，这个时候问问题我倒是体验过了——我问的她可以听懂，她回答的我完全听不懂……

不过，我肯定不会这样放弃一个大好的机会，于是找英语老师问可不可以帮助翻译。老师让我把问题写下来，我又说要不然下课过后我去你办公室问，老师同意了。

既然得到了这样的好机会，于是我赶紧绞尽脑汁写了几条

1. 在你们的国家的标牌上有中文吗？多吗？如果我不懂英文会在那里寸步难行吗？
2. 你们的教育方式&理念是什么样的？你又如何看待中国的应试教育？
3. 在你们的历史书中，会学中国的历史吗？是什么样的？例如，你知道唐吗？民国吗？
4. ~~这个问题或许有些冒犯，但我想知道俄乌战争给你带来了怎样的影响？（后被英语老师剔除，因为涉政。）~~
5. 你们经常喝咖啡吗？
6. 可以签名吗？

到了办公室，英语老师先和她们针对这些问题深度交谈，然后讲梗概告诉我——所以我也就只能复述出来梗概了。

第一个问题，老外说有，且很多。来自俄罗斯的那位还说，不会寸步难行，俄罗斯人看似又一些冷漠，但是如果你上前问他们，他们会非常乐意帮助你——就像中国人一样 friendly

第二个问题英语老师只给我说普天之下的教育都是一样的，都是要奋斗的。但是我还隐隐约约听到了老外不仅说了这个，还说了 我们那边的自由时间更多一些 。不过，我想英语老师这样说是为了不让我丧气吧。

第三个问题。来自南美洲智利的老外说他们根本不教，而俄罗斯人说他们的历史课和中国类似，都是本地历史+国际历史的，所以也有所涉及。

第五个问题则自然是经常喝——不过二人都表达她们更乐意喝茶。

最后签名自然是要到了，而且还给我多写了一句话！不仅如此，还拍了合照。

顺便说一句，来自智利的教授是用左手写字的，书会向右90度倾斜写，我也不知道为什么，但是出于尊重，我没有问。

另外，本来准备问她们有没有博客的，但是这个问题是当时临时想到的，结果后来搞忘了，挺可惜的。

![image.png](https://blog.owenzjg.com/static/img/7e277ee8e1f134f5c70993a1d1027068.image.webp)
# so
大致就是这样了，这次交流给我英语的提升倒是没有什么，不过，对外国我却了解到了不少。

着是和外国人交流的另一个路程，第一个是和外国人的少量交谈，这篇文章，而现在，又是一大步。

希望以后可以 more and more 的与外国人交往吧。

后会有期。

和老外的深交

这并不是我第一次谈论人工智能了，当然，也并不是最后一次。

在当今的这个时代下，这个话题是不可避免的，也是不断进步、不断发展的。




# 前沿的说明
 在[ChatGPT与人工智能 ](./14) 这篇文章中，我就描述过了对人工智能发展的一些看法。不过，这篇文章讨论的方向会不太一样。
 
 在那篇文章中，我是以现有的人工智能技术进行分析和展望，不过，在这种基调下，似乎和人工智能这个大的话题不太相称，因为，似乎 ChatGPT 也并没有达到我们心目中的对人工智能的定义。
 
 既然现在还没有这种机器人，我们就只好展望未来，在文学小说的影子里来探寻了。这里主要分析和讲述的是《阿西莫夫机器人短片全集》，也是我对这方面的启蒙书。
 
 话说读到这本书，确实纯属巧合。我已经不记得我是如何在图书馆的茫茫书海中正好看到它的，又选中了它。
 
 不过既然选择了它，我就踏踏实实的读完了，这也是我对人工智能和机器人的最初理解。不过那个时候我大概也就是小学的四五年级，并没有非常深入的思考。
 
 后来，在初一的时候， ChatGPT 的出现让 人工智能 这个词汇重新开始火爆起来，而这本书，也被我拿出来，细细品读。
 
 这，大概就是我和这本书的渊源了，接下来介绍一下这本书本身的内容吧。
 
 这本书大部分内容创作于 1939～1977 ，写于很长时间以前，却又犹如当代作家的推理思维。不得不赞叹作家的文学功底和文字的美妙。
 
 话说这本书的内容，本来就是小说，但是现在似乎成了机器人的研究方向。例如「机器人学」这个概念就首创于这本书的《转圈圈》当中，而机器人学三大法则也变得家喻户晓，甚至成为了现在研究机器人的方向。
 
 至于文章中的内容，则允许我有所保留，等到后文分析人工智能的时候一起讲。
 
> **机器人学三大法则**
 >1. 机器人不得伤害人类，或因不作为而使人类受到伤害。
 >2. 除非违背第一法则，机器人必须服从人类的命令
 >3. 在不违背第一及第二法则的情况下，机器人必须保护自己
# 人工智能
这个部分，我先笼统的讲述，然后逐渐笼罩到三大法则上来分析吧。

## 畏惧
不得不说人们对于人工智能的畏惧情绪一直是有的。

先说说阿西莫夫的短篇小说当中吧，机器人甚至不允许在地球——甚至别的人类殖民地上活动，人类也从来没有接受他们——大部分的机器人都用在了太空探险上面。

而生活中的人们，又何尝不是这样呢？

上次去体测的路上，在大巴车上和另外一些人聊天，感到了一阵可悲。有一个人自作聪明的一本正经的给我讲「ChatGPT 可以自我迭代，到后来人类也不知道它是如何发展的，到最后人类甚至无法关停它，因为即是是最厉害的黑客也无法搞懂它的原理」。

我试图给他解释了好久，但是他似乎油盐不进，我也懒得辩解了。旁边的另外一个人似乎被我说服了，但是嘴里还是不停的念叨「好可怕，好可怕」。

不得不说，人工智能在人类的潜意识里是一个很好的工具，但是同时，也是人类的天敌——另外一个可怕的物种。

就这样，产生了三大法则，不得不说，这个对机器人的束缚是非常大的，而且本身也有一定的缺陷，可是似乎怎样修改都会产生微小的毛病。

这个后面且继续分述，然而这样的法则也限制不了人们的恐惧和抵触的心理。就这样，阿西莫夫创作了一系列引人同情的机器人——如《小机》。

这些机器人即使对人类一丁点威胁都没有，似乎人类也惧怕他们——惧怕他们懂得的如此的多，如此的能干，如此的完美无缺。所以，不顾一切的想把它赶走。

不过这种情况似乎也归结于人类的另一种性格，为了讨厌而讨厌，一旦产生了讨厌的感觉，则似乎机器人干什么都是讨厌的。

## 三大法则

三大法则是什么前文已经有了，而每一条分别代表不同的等级。

首先，机器人不可以伤害人类——也就是说，彻底阻断了人类被机器人灭种消灭的想法。

但是，这并不够。万一他们并不伤害人类，但是依然取代了人类怎么办呢？于是，这些机器人必须乖乖听话，使得机器人彻底被限制在人类之下。

最后的最后，花钱买来的机器人不能说坏就坏，所以才规定它们必须保护自己。

说实话，这似乎又一些奴隶的意味在里面了，不是吗？奴隶伤害奴隶主的性命，那是不可能的事情。而违抗奴隶主的指令，伤害奴隶主的利益，也是不能被允许的。最后，才让这些奴隶苟活着。

而且，他们似乎还比奴隶更加卑贱，因为它们根本不会反抗——奴隶或许有极少数会逃走，但是这三大法则的路径却永远也绕不开。

### 1

介绍了一下对三大法则的初步感受，现在来细细的品味一下。

首先，这个伤害人类的界限到底是什么？似乎并不是很清楚。机器人把这个贯彻的非常到位，例如在《骗子！》中，就是一个无意制造出来的可以看透心灵的机器人为了不伤害人类而被迫说谎。也就是说，丝毫的心灵上的波动或难受都是伤害。

而在《消失无踪》的前半段，人正常在这种射线（我记得是伽玛射线）中待20分钟不会有什么影响，但是机器人坚持说这样有风险受伤，把人们抱出来。当然，后面它们弱化了第一法则引发的一系列故事，就另说了。

由此可以看来，第一法则的界限是非常的广的，但是似乎在某些时候它也一定程度上造成了机器人功能上的阻碍和障碍。但是如果你试图修改它们，那稍不留神又会制造一个诸如《消失无踪》的找机器人惨案。

另外，牺牲如果不可避免，那么谁牺牲最合适？在大部分的小说中，都是以数量来决定——如果五个老头和一个天才，则会牺牲天才。

于是，就有了《三百年庆事件》，机器人觉得杀掉总统而自己来接任会对整个社会有利。当然，这个对人类所产生的影响也不免又一些太大了，所以，幕后有一个人来帮助、协助。

当然，相对来说和缓一些的，机器人就没有借助人类了。比如《可避免的冲突》就是讲述了机器人为了避免冲突而把几个人调离岗位或者引人怀疑。

### 2

刚才大致讲述了一下第一法则，那现在再来说一说第二法则吧。

第二法则的缺陷似乎非常的明显，就是不管是坏人还是好人都可以利用。

最明显的就是《校工》，当然这个也部分利用了第一法则，但是我们不妨把它们归为一类。文中的教授为了反对机器人，而故意让把机器人校对过的手稿调包，换成一些严重侵害他人的词句。这个事件最后也是他自己无意让机器人以为打破沉默为这个教授辩解比教授以前的要求沉默更重要。而教授却以为这个机器人要揭穿自己，于是无意说漏了嘴。

确实，这个事情最后处理了，但是也必须是当事人的无意和粗心，以及一定的引诱才解决的。那么如果当事人精通机器人心理学，没有上钩，该怎么办？

### 3

第三法则倒是没有什么单独的论述。不过后面又一些修改的法则和第三法则可以扯上关系。

## 被修改的法则
前文或许也不经意间讲到了，如「《消失无踪》的找机器人惨案」，不过，现在会更加详细的讲述。

这篇文章的起因就是机器人太过于珍贵，所以第三法则被加强了，而第二法则又没有用很强的预期来描述，于是机器人在某个点就达到了两个法则的平衡，于是就在原地转圈圈。最后就不得不用差点牺牲来触发第一法则，让机器人来摆脱二三的平衡。

这个故事仿佛展现了下达命令必须要用强硬的口吻才可以强调这是一个命令。可是这样又似乎过于残酷，不符合人类的基本道德观念。

---
至于第一法则被弱化，则后果更加严重。例如前文说过的《消失无踪》，就是由于第一法则的弱化而导致机器人对人类的鄙视。当然，程度没有那样的深，但是，也造成了一定的后果，机器人努力从人类的命令中找刺，最后险些逃走。

---

就没有一种方法可以给机器人加入一种道德观念而改善三大法则的缺陷吗？比如下达命令的优先级和保护的优先级。确实有，比如在《……汝竟眷顾他》当中就有。可是在考虑所有的因素过后——两个机器人发现，机器人比人更有资格当人。

# 最后
这篇文章大多数是从阿西莫夫的小说的角度来说的。

说实话，打的又一些累，你现在的版本也不是最后的版本，我还没有写完——或者准备再写一个，专门逐个剖析阿西莫夫的小说。

当然，这篇文章的语序比较乱，我也会后期修改。

不过，今天这么晚，打了这么多字，就先放一放吧。

后会有期！

阿西莫夫和人工智能

这篇帖子主要讲的是人工智能。





进入正题，我们今天要介绍的是人工智能模型的决策树。下面可以通过一个简单的例子来了解。

【决策树a】

参数为age，表示年龄;

            如果age >= 16 那么{

                可以骑电瓶车;

            }

            不然的话{

                不可以骑电瓶车;

            }

这是一个简单的决策树，用于判断应该给 ~~受害人~~ 用户推送怎样的工具。

但是真实情况很复杂。想必抖音大家都玩过，你用的越久，你就会发现，抖音给你推送的东西都很符合你的喜好。而仅靠这么几行的决策树，是不可能解决这样的问题的。

那我们要怎么解决呢，答案是： ~~写一万个if~~ 使用人工智能

在没有人工智能的年代，写各种程序全靠肝，但是现在我们有人工智能了，自然要用人工智能解决。

如果想用人工智能解决这个问题的话，就需要先训练一个**模型**。

**模型**是什么？

简而言之，模型就是一种类似于函数的东西。他需要你传入参数，例如上面的【决策树a】，需要传入参数age，然后经过它一顿计算，最后会返回要给用户推送啥。

那要如何训练模型？

想要训练模型，就必须要有数据。我们的模型不仅要训练，还要看看它训练的怎么样。所以，我们需要把数据进行拆分。通常，拆分的最佳比例为7:3（7是训练，3是评估）。

接下来，我们要拿训练数据去训练模型。由于本文只是介绍基本概念，没有放代码，所以说这些可以自行了解。

训练好的模型还要拿去评估。我们使用测试数据去测试模型。接下来才是本文的关键：

想必大家都想到了，有一种评估方式叫做“平均正确率”。一般平均正确率大于90%以上的都是好模型。

例如有100个测试数据，对了94个，那么这个模型的正确率就是94%，是好模型。

但是你们觉得这个办法他就一定可靠吗？

假设我们瞎写了一个性别判断模型，不管传入的参数是什么，他都会输出“男”，而我们的测试数据有10个，9个数据的正确答案都是“男”，只有一个的正确答案是“女”，那么你们想想，这个模型的正确率是多少？这个模型好吗？

显而易见，这个模型的正确率高达90%，但是如果把他投入到实际应用，估计全天下的女生都得要变性。所以说，我们还有一个判断标准，叫“**召回率**”。

召回率要怎么计算呢？我们先把测试数据里的结果为女的**暂时**删掉，再评估一遍平均正确率，显然，是100%。

然后，再去掉男的，让模型在女队里评估一遍，显然，正确率为0%。

随后，我们就知道了，这个模型男的召回率为100%，女的召回率为0%。通常，我们评估模型都是先评估一遍平均正确率，在评估一遍各个结果对应的召回率。只有当所有数值都大于90%的时候，这个模型才算是好模型。

这个垃圾的性别判断模型，平均正确率为90%，男的召回率为100%，女的召回率为0%，而这个模型女的召回率明显不达标，所以这个模型十分垃圾。

今天就先讲到这，期待下一讲吧！

人工智能-决策树-1

这篇文章，将要分析luogu题单「[【算法2-2】常见优化技巧](https://www.luogu.com.cn/training/201#problems)」中的所有题目。

在讲解的过程中，会了解到许多常见的优化技巧。


看完此文，你就会解决上述题单里的所有题目，及一下题目：
- P1102 A-B 数对
- P1638 逛画展
- P1115 最大子段和
- P7072 [CSP-J2020] 直播获奖
- P2671 [NOIP2015 普及组] 求和
- P4147 玉蟾宫
- P2866 [USACO06NOV] Bad Hair Day S
- P1950 长方形
- P2032 扫描
- P2216 [HAOI2007] 理想的正方形
- UVA11572 唯一的雪花 Unique Snowflakes
- P4653 [CEOI2017] Sure Bet
- P3143 [USACO16OPEN] Diamond Collector S
- P7910 [CSP-J 2021] 插入排序
- P1578 奶牛浴场
- P3467 [POI2008] PLA-Postering
- P1886 滑动窗口 /【模板】单调队列
- P2880 [USACO07JAN] Balanced Lineup G
- P1714 切蛋糕
- P1725 琪露诺

## [P1102 A-B 数对](https://www.luogu.com.cn/problem/P1102)

![image.png](https://blog.owenzjg.com/static/img/4773bbc447d348cab463e1536bf5ef67.image.webp)

这个题目的大致意思就是在一组数中找到一对 $A,B$ ，使得他们满足 $A-B=C$

这题首先也是最容易想到的思路就是双重循环枚举法，不用说，这种方法必定超时，这里不做过多的介绍。

如本文标题所言，我们要学习「常见优化技巧」，这里就介绍一个方法——**转换法**。

**我们可以把原有的条件、等式等进行转化，变成另一种更易计算的形式。**

如这题的式子就可以转换为 $A-C=B$。

也就是说，我们只要判断是否有一个数比 $A$ 小 $C$ ，如果有，那么就加上其个数。

这让人很容易想起来「桶」算法。但是，这一题的数据范围比较大，所以我们就要用到 c++ 自带的 STL ， `map` 。

其实并不是什么高级的东西，只不过是一个可以开的非常大的数组，调用方法等和普通数组没有区别。

确定下来了思路，我们就可以开始写了。不过这里有一个比较坑的地方，就是题目输入的数组是没有排序的，所以需要手动排序。这样，时间复杂度就是 $O(nlogn) $

```cpp
#include <bits/stdc++.h>
using namespace std;
#define ll long long
map<ll, ll> t;
ll a[200000 + 10];
int main() {
    ll n, c;
    cin >> n >> c;
    ll cnt = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        t[a[i]]++;
    }
    sort(a + 1, a + 1 + n);
    for (int i = 1; i <= n; i++) {
        cnt += t[a[i] - c];
    }
    cout << cnt;
    return 0;
}
```

当然，我们还可以进行优化，我们把中间的`sort(a + 1, a + 1 + n);`也就是排序去掉也可以。

因为即使这个时候没有排序了，但是我们已经把 `cnt += t[a[i] - c];` 单独放在了一个 `for` 里面，所以这种情况下不会有少算比它小的数的情况，因为所有的数都录入完了，而 `cnt` 加的顺序其实是无所谓的。

所以，以下是最终优化的程序
```cpp
#include <bits/stdc++.h>
using namespace std;
#define ll long long
map<ll, ll> t;
ll a[200000 + 10];
int main() {
    ll n, c;
    cin >> n >> c;
    ll cnt = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        t[a[i]]++;
    }
    for (int i = 1; i <= n; i++) {
        cnt += t[a[i] - c];
    }
    cout << cnt;
    return 0;
}
```
## [ P1638 逛画展](https://www.luogu.com.cn/problem/P1638)

![image.png](https://blog.owenzjg.com/static/img/e06b5569ee2b5f2fd6627fbaef1d0ff3.image.webp)

这个题目的主要意思非常的明显。首先，我们定义一个区间内的数如果囊括了 $M$ 位画家，我们就称其为 「满足条件的区间」，则问这个区间的长度的最小值。

这个题目要用到一个非常常见的优化技巧 ——「**滑动窗口**」（当然，这个算法还有很多的名字，重点只算法的本质）

我们维护一个窗口——或者说区间。左端点是 `l`，右端点是`r`。

我们要保证这个区间是符合题目要求的区间。所以

- 当区间不满足题目要求的时候，我们就使区间 `r++` ，吸纳更多的元素，这样就可以让区间符合题目的要求。
- 当区间已经符合了题目的要求后，我们就让区间 `l++` ，减少元素，尽量让区间变得更小，直到区间不再满足题目要求为止。

这个就是这个算法的基本思想，接下来我们带入到题目当中去计算。

其实这类题目的代码较为模板，主要就是要寻找到其区间知否满足题目要求的要点。

我们先准备一个 `l` 和 `r` ，由于在循环中 `r` 还需要 `++` ，所以先赋值为 0。

```cpp
int l = 1, r = 0;
```

接下来就要进入循环的环节。循环的判断值就是这个区间走向了尽头，也就是说 `r` 在下一步的时候会超出 $N$ 的界限。判断如下：`r + 1 <= n`

我们先讨论前面的「当区间不符合题目要求」的这种情况，我们就让 `r` 按照惯例往后推一个，然后记录这个数字。如果这是一个新的数字，我们就让 `cnt++` ，来记录区间里面不同的数的个数。

```cpp
r++;
t[a[r]]++;
if (t[a[r]] == 1) {
    cnt++;
}
```

然后，我们来讨论「符合题目要求」的情况。判断条件为 `cnt == m` 当满足这个情况的时候，我们要先尽量的「紧区间」，也就是把臃肿的部分去掉。

如果去掉这个并不会影响不同的数的个数，也就是在这个区间内还有这个数的话，而且 `l` 没有超过 `r` ，则这个数可以去掉。浴室就产生了这个循环。

```cpp
while (l + 1 <= r && t[a[l]] != 1) {
    t[a[l]]--;
    l++;
}
```

最后记录一下最小值，为基本内容，不做讲述。

```cpp
if (r - l + 1 < minn) {
    mina = l;
    minb = r;
    minn = r - l + 1;
}
```

把上述模块组合在一起，就是如下AC代码。

```cpp
#include <bits/stdc++.h>
using namespace std;
#define maxn 1000000
int a[maxn + 10];
int t[2000 + 10];
int cnt = 0;
int minn = maxn + 10;
int mina, minb;
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int l = 1, r = 0;
    while (r + 1 <= n) {
        r++;
        t[a[r]]++;
        if (t[a[r]] == 1) {
            cnt++;
        }
        if (cnt == m) {
            while (l + 1 <= r && t[a[l]] != 1) {
                t[a[l]]--;
                l++;
            }
            if (r - l + 1 < minn) {
                mina = l;
                minb = r;
                minn = r - l + 1;
            }
        }
    }
    cout << mina << " " << minb;
    return 0;
}
```
## [P1115 最大子段和](https://www.luogu.com.cn/problem/P1115)

![image.png](https://blog.owenzjg.com/static/img/45660a6b9c7c77e61b787561a7d3e70a.image.webp)

题目的主要意思非常的清楚，求所以连续非空区间的和的最大值。

这个有点类似于滑动窗口，但是差别非常的大，我们就样例分析。
```txt
7
2 -4 3 -1 2 -4 3
```
选中第一个数字 2 后。后面的数字是 -4 。如果 -4 在这个答案区间里，那么 2 肯定也在，因为可以增加区间的和。

选中第二个数字 -4 后，后面的数字是 3 。这个时候就必须舍弃掉 2 和 -4 了，因为他们的和事 -2 ，对于3 没有任何好处。

选中第三个数字 3 并且舍弃掉前面的数字后，和变成了3 。这个时候 -1 肯定要 3 ，因为有助于区间和的增加。

后面的数字以此类推。

这个时候我们就可以分析出来算法了。如果前面的窗口加上这个数不如这个数本身大的时候，也就是前面的窗口是负数的时候，我们就可以舍弃掉这一段，从新开始计数。

下面开始着手写代码。

首先我们默认区间选中了第一个数，也就是有如下代码
```cpp
int maxx = a[1];
int cnt = a[1];
```

在循环当中，如上所说，当前的窗口的和为如下选择：

- 如果当前的和为负数，也就是加上这个数比这个数本身小的时候，我们就从新开始窗口，当前的数是新窗口的第一个数，窗口的和是这个数
- 如果当前的和为正数，也就是加上这个数比这个数本身大的时候，我们就延续这个窗口，和加上这个数。

最后取最大值。

于是就有了如下代码
```cpp
for (int i = 2; i <= n; i++) {
    cnt = max(a[i], cnt + a[i]);
    maxx = max(maxx, cnt);
}
```

上面就是核心代码的解析，这个是所有的代码

```cpp
#include <bits/stdc++.h>
using namespace std;
int a[200000 + 10];
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int maxx = a[1];
    int cnt = a[1];
    for (int i = 2; i <= n; i++) {
        cnt = max(a[i], cnt + a[i]);
        maxx = max(maxx, cnt);
    }
    cout << maxx;
    return 0;
}
```
## [P7072 [CSP-J2020] 直播获奖](https://www.luogu.com.cn/problem/P7072)

![image.png](https://blog.owenzjg.com/static/img/c7122fb362097258c5d75b6af6eeb67a.image.webp)
这个题目的大致意思就是按照一系列算法，求出实时得奖人数，并且从大到小得出的奖分数线。

这个题目的难点在于，我们要绕过常规思维——每次输入一个数都要重新排序。

这里先介绍一个非常常见的优化方法——「**桶排序**」

这个算法的方式就是准备一个数组，数组的大小就是所有要处理的数的最大值。

便利所有的数，将数的值作为下标的元素加一。换成公式就是这样的。 $t[A_i]++$

然后从最大值便利到最小值，输出。我们设定最大值是 `maxx` 那么遍历代码如下

```cpp
for (int i = maxx; i >= 0; i--) {
    for (int j = 1; j <= t[i]; j++) {
        cout << i << " ";
    }
}
```
这个就是「桶排序」的基本思想。与用到这题上面，我们就可以输入一个数后将其装入桶，每次再从大到小便利，由于每个数的数据范围不大，所有这道题目就引刃而解了。

首先先输入并且装桶。

```cpp
int a;
cin >> a;
t[a]++;
```
然后根据题目里面的内容计算现在的「计划获奖人数」
```cpp
int people = 1;
people = max(people, i *w / 100);
```
然后再想上文一样，从大到小便利，每次计算当前学生总数，超过或者到达「计划获奖人数」后停止，然后输出。
```cpp
int cnt = 0;
for (int j = 600; j >= 0; j--) {
    cnt += t[j];
    if (cnt >= people) {
        printf("%d ", j);
        break;
    }
}
```
这就是核心部分，其它的部分就是一些输入输出等非重点，可以自行查看代码。
```cpp
#include <bits/stdc++.h>
using namespace std;
int t[1000];
int main() {
    int n, w;
    cin >> n >> w;
    for (int i = 1; i <= n; i++) {
        int a;
        cin >> a;
        t[a]++;
        int people = 1;
        people = max(people, i * w / 100);
        int cnt = 0;
        for (int j = 600; j >= 0; j--) {
            cnt += t[j];
            if (cnt >= people) {
                printf("%d ", j);
                break;
            }
        }
    }
    return 0;
}
```


:::warning{title="注意"}
这篇文章还没有结束，但是由于篇幅预估会很长，写作时间跨度大，所以先发布。
:::