本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AtCoderC - Seating Arrangement【题目描述】Takahashi is in charge of arrangingN NNseats lined up in a row at a cultural festival venue. The seats are numbered1 11throughN NNfrom left to right.高桥负责安排文化节会场上一排N NN个座位的安排。座位从左到右编号为1 11到N NN。Currently, some seats are already occupied by guests. Specifically, seati iiis occupied ifS i 1 S_i 1Si​1, and vacant ifS i 0 S_i 0Si​0.目前一些座位已经被客人占据。具体来说如果S i 1 S_i 1Si​1则座位i ii已被占据如果S i 0 S_i 0Si​0则座位i ii为空。Takahashi can select0 00or more vacant seats as he likes and guide one new guest to each selected seat. However, he cannot move or remove guests who are already seated. Also, each seat can hold at most1 11person. Furthermore, due to the venue’s ventilation rules, the following condition must be satisfied:高桥可以任意选择0 00个或更多空座位并引导一位新客人到每个选中的座位。但是他不能移动或移除已经就坐的客人。同时每个座位最多容纳1 11人。此外由于会场的通风规定必须满足以下条件After all guests have been guided to their seats, there must beno three consecutive seats that are all occupied.在所有客人被引导到座位后不能存在三个连续的座位全部被占据。In other words, if we denote the state of seati iiafter all guidance is complete asT i T_iTi​(1 11if occupied,0 00if vacant), then for everyi iisatisfying1 ≤ i ≤ N − 2 1 \leq i \leq N-21≤i≤N−2, it must not be the case thatT i T i 1 T i 2 1 T_i T_{i1} T_{i2} 1Ti​Ti1​Ti2​1. It is guaranteed in the input that the initial state already satisfies this condition.换句话说如果用T i T_iTi​表示引导完成后座位i ii的状态1 11表示被占据0 00表示空那么对于每个满足1 ≤ i ≤ N − 2 1 \leq i \leq N-21≤i≤N−2的i ii不能有T i T i 1 T i 2 1 T_i T_{i1} T_{i2} 1Ti​Ti1​Ti2​1。输入保证初始状态已满足此条件。Takahashi wants to guide as many new guests as possible while satisfying this condition. Find the maximum number of new guests that can be guided.高桥希望在满足此条件的情况下引导尽可能多的新客人。求可以引导的新客人的最大数量。【输入】N NNS 1 S_1S1​S 2 S_2S2​… \ldots…S N S_NSN​The first line contains an integerN NNrepresenting the number of seats.The second line containsN NNintegersS 1 , S 2 , … , S N S_1, S_2, \ldots, S_NS1​,S2​,…,SN​separated by spaces, representing whether each seat is occupied.S i 1 S_i 1Si​1means seati iiis occupied, andS i 0 S_i 0Si​0means it is vacant.【输出】Print in one line the maximum number of new guests that can be guided while satisfying the condition.【输入样例】5 0 0 1 0 0【输出样例】2【算法标签】#贪心#【代码详解】#includebits/stdc.husingnamespacestd;constintN200005;intn,ans;ints[N];// 整数数组存储座位状态0表示空1表示已占intmain(){cinn;// 输入座位数量// 读取n个整数的座位状态for(inti1;in;i){cins[i];}// 遍历每个座位for(inti1;in;i){if(s[i]1)// 如果当前座位已经有人跳过{continue;}boolflagtrue;// 标记当前座位是否可以安排新客人// 情况1检查是否形成1 0 1的模式即左右座位都有人if(i1ns[i-1]1s[i1]1){flagfalse;// 不能安排否则会形成1 1 1}// 情况2检查左边是否已经有两个连续的1elseif(i3s[i-2]1s[i-1]1){flagfalse;// 不能安排否则会形成1 1 1}// 情况3检查右边是否已经有两个连续的1elseif(i2ns[i1]1s[i2]1){flagfalse;// 不能安排否则会形成1 1 1}// 如果当前座位可以安排新客人if(flag){s[i]1;// 将座位标记为已占用ans;// 增加安排的客人数量}}coutansendl;// 输出最大可安排的客人数量return0;}【运行结果】5 0 0 1 0 0 2