尧图网站开发 
本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】瑞学堂徐老师的团队活动【题目描述】徐老师最近准备给同学们组织团队活动——猫捉老鼠但是选多少人当猫选哪些人成了问题每个同学的体力热衷程度均不同有的人希望当猫去抓人有的人希望自己团队的人数多一些…于是徐老师统计了每个人的如果被选作当老鼠逃跑时他希望的团队人数a i a_iai如果第i ii位同学被选中当老鼠那么他希望老鼠团队的人数是超过a i a_iai的这样自己不容易被抓如果第i ii位同学被选中当猫那么他希望老鼠团队的人数是少于a i a_iai的这样作为猫的一方自己更容易获得胜利现在徐老师想知道有多少选择方案可以满足每个同学的希望呢每个人必须要么是老鼠要么是猫P.S. 这里注意允许所有同学都当老鼠或者都当猫此时可以由许老师来担任另一个身份并且许老师不算在团队人数内【输入】输入第一行包含一个整数n nn表示一共有多少同学输入第二行包含n nn个整数分别表示第i ii个人的希望团队人数a i a_iai【输出】输出一个整数表示有多少种选择方案【输入样例】4 0 3 3 2【输出样例】2【核心思想】问题分析给定n nn位同学每人有一个希望值a i a_iai。若选为老鼠要求老鼠团队人数x a i x a_ixai若选为猫要求老鼠团队人数x a i x a_ixai。求所有满足每个人希望的选择方案数。这是一个排序后枚举 贪心验证问题关键在于发现最优策略是将a i a_iai排序后选择前x xx小的人当老鼠后n − x n-xn−x大的人当猫只需验证边界条件。算法选择排序Sort将a i a_iai从小到大排序使得前x xx位当老鼠、后n − x n-xn−x位当猫的贪心策略成立贪心策略排序后a i a_iai越小的人越适合当老鼠因为老鼠要求x a i x a_ixaia i a_iai小更容易满足a i a_iai越大的人越适合当猫枚举验证枚举老鼠团队人数x xx从0 00到n nn利用排序后的单调性只需检查边界元素关键步骤读取与排序读入n nn和数组a [ 1.. n ] a[1..n]a[1..n]将a aa从小到大排序枚举x xx老鼠团队人数从0 00到n nn边界情况x 0 x 0x0全猫检查a 1 0 a_1 0a10x n x nxn全鼠检查a n n a_n nann一般情况0 x n 0 x n0xn前x xx位老鼠最大希望值为a x a_xax需满足a x x a_x xaxx老鼠人数超过其希望后n − x n-xn−x位猫最小希望值为a x 1 a_{x1}ax1需满足a x 1 x a_{x1} xax1x老鼠人数少于其希望即验证a[x] x a[x1] x统计答案满足条件的x xx个数即为方案数时间/空间复杂度时间复杂度O ( n log n ) O(n \log n)O(nlogn)排序O ( n log n ) O(n \log n)O(nlogn)枚举验证O ( n ) O(n)O(n)空间复杂度O ( n ) O(n)O(n)存储数组a aa贪心 排序的核心思想排序创造单调性排序后前x xx位必然是最容易满足当老鼠条件的人a i a_iai小后n − x n-xn−x位是最容易满足当猫条件的人a i a_iai大贪心选择最优边界压缩验证排序后只需检查分界处的两个元素a x a_xax和a x 1 a_{x1}ax1无需遍历所有人利用单调性将O ( n ) O(n)O(n)验证降为O ( 1 ) O(1)O(1)枚举与贪心的结合枚举所有可能的团队人数x xx但利用排序后的结构使每次验证极高效全选边界处理x 0 x0x0和x n xnxn时分别只需检查最值体现贪心策略的完备性适用于将集合划分为两部分每部分有独立约束且约束具有单调性的划分计数问题【算法标签】#贪心【代码详解】#includebits/stdc.husingnamespacestd;constintN100005;// 定义数组最大容量为100005intn,ans;// n为同学数量ans记录满足条件的选择方案数inta[N];// a[i]表示第i位同学希望的团队人数// 检查选择x位同学当老鼠、n-x位同学当猫是否满足所有人的希望// 策略将a数组排序后选择前x位同学当老鼠希望团队人数a_i即a_ix后n-x位当猫希望团队人数a_i即a_ixboolcheck(intx){if(x0)// 所有同学都当猫老鼠团队人数为0{returna[1]0;// 所有人都希望老鼠团队人数a_i即a_i0只需检查最小的a[1]}elseif(xn)// 所有同学都当老鼠老鼠团队人数为n{returna[n]n;// 所有人都希望老鼠团队人数a_i即a_in只需检查最大的a[n]}else// x位同学当老鼠n-x位同学当猫{// 前x位当老鼠需要a_i x老鼠团队人数x a_i// 后n-x位当猫需要a_i x老鼠团队人数x a_i// 排序后只需检查边界第x位最大的老鼠和第x1位最小的猫return(a[x]x)(a[x1]x);}}intmain(){cinn;// 读入同学数量nfor(inti1;in;i)// 读入每位同学希望的团队人数cina[i];sort(a1,an1);// 将希望人数从小到大排序便于二分/枚举边界// 枚举老鼠团队人数x从0到n检查每种方案是否可行for(inti0;in;i){if(check(i))// 如果x位老鼠的方案满足所有人的希望ans;// 方案数加1}coutansendl;// 输出满足条件的选择方案总数return0;}【运行结果】4 0 3 3 2 2 
本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】瑞学堂徐老师的团队活动【题目描述】徐老师最近准备给同学们组织团队活动——猫捉老鼠但是选多少人当猫选哪些人成了问题每个同学的体力热衷程度均不同有的人希望当猫去抓人有的人希望自己团队的人数多一些…于是徐老师统计了每个人的如果被选作当老鼠逃跑时他希望的团队人数a i a_iai如果第i ii位同学被选中当老鼠那么他希望老鼠团队的人数是超过a i a_iai的这样自己不容易被抓如果第i ii位同学被选中当猫那么他希望老鼠团队的人数是少于a i a_iai的这样作为猫的一方自己更容易获得胜利现在徐老师想知道有多少选择方案可以满足每个同学的希望呢每个人必须要么是老鼠要么是猫P.S. 这里注意允许所有同学都当老鼠或者都当猫此时可以由许老师来担任另一个身份并且许老师不算在团队人数内【输入】输入第一行包含一个整数n nn表示一共有多少同学输入第二行包含n nn个整数分别表示第i ii个人的希望团队人数a i a_iai【输出】输出一个整数表示有多少种选择方案【输入样例】4 0 3 3 2【输出样例】2【核心思想】问题分析给定n nn位同学每人有一个希望值a i a_iai。若选为老鼠要求老鼠团队人数x a i x a_ixai若选为猫要求老鼠团队人数x a i x a_ixai。求所有满足每个人希望的选择方案数。这是一个排序后枚举 贪心验证问题关键在于发现最优策略是将a i a_iai排序后选择前x xx小的人当老鼠后n − x n-xn−x大的人当猫只需验证边界条件。算法选择排序Sort将a i a_iai从小到大排序使得前x xx位当老鼠、后n − x n-xn−x位当猫的贪心策略成立贪心策略排序后a i a_iai越小的人越适合当老鼠因为老鼠要求x a i x a_ixaia i a_iai小更容易满足a i a_iai越大的人越适合当猫枚举验证枚举老鼠团队人数x xx从0 00到n nn利用排序后的单调性只需检查边界元素关键步骤读取与排序读入n nn和数组a [ 1.. n ] a[1..n]a[1..n]将a aa从小到大排序枚举x xx老鼠团队人数从0 00到n nn边界情况x 0 x 0x0全猫检查a 1 0 a_1 0a10x n x nxn全鼠检查a n n a_n nann一般情况0 x n 0 x n0xn前x xx位老鼠最大希望值为a x a_xax需满足a x x a_x xaxx老鼠人数超过其希望后n − x n-xn−x位猫最小希望值为a x 1 a_{x1}ax1需满足a x 1 x a_{x1} xax1x老鼠人数少于其希望即验证a[x] x a[x1] x统计答案满足条件的x xx个数即为方案数时间/空间复杂度时间复杂度O ( n log n ) O(n \log n)O(nlogn)排序O ( n log n ) O(n \log n)O(nlogn)枚举验证O ( n ) O(n)O(n)空间复杂度O ( n ) O(n)O(n)存储数组a aa贪心 排序的核心思想排序创造单调性排序后前x xx位必然是最容易满足当老鼠条件的人a i a_iai小后n − x n-xn−x位是最容易满足当猫条件的人a i a_iai大贪心选择最优边界压缩验证排序后只需检查分界处的两个元素a x a_xax和a x 1 a_{x1}ax1无需遍历所有人利用单调性将O ( n ) O(n)O(n)验证降为O ( 1 ) O(1)O(1)枚举与贪心的结合枚举所有可能的团队人数x xx但利用排序后的结构使每次验证极高效全选边界处理x 0 x0x0和x n xnxn时分别只需检查最值体现贪心策略的完备性适用于将集合划分为两部分每部分有独立约束且约束具有单调性的划分计数问题【算法标签】#贪心【代码详解】#includebits/stdc.husingnamespacestd;constintN100005;// 定义数组最大容量为100005intn,ans;// n为同学数量ans记录满足条件的选择方案数inta[N];// a[i]表示第i位同学希望的团队人数// 检查选择x位同学当老鼠、n-x位同学当猫是否满足所有人的希望// 策略将a数组排序后选择前x位同学当老鼠希望团队人数a_i即a_ix后n-x位当猫希望团队人数a_i即a_ixboolcheck(intx){if(x0)// 所有同学都当猫老鼠团队人数为0{returna[1]0;// 所有人都希望老鼠团队人数a_i即a_i0只需检查最小的a[1]}elseif(xn)// 所有同学都当老鼠老鼠团队人数为n{returna[n]n;// 所有人都希望老鼠团队人数a_i即a_in只需检查最大的a[n]}else// x位同学当老鼠n-x位同学当猫{// 前x位当老鼠需要a_i x老鼠团队人数x a_i// 后n-x位当猫需要a_i x老鼠团队人数x a_i// 排序后只需检查边界第x位最大的老鼠和第x1位最小的猫return(a[x]x)(a[x1]x);}}intmain(){cinn;// 读入同学数量nfor(inti1;in;i)// 读入每位同学希望的团队人数cina[i];sort(a1,an1);// 将希望人数从小到大排序便于二分/枚举边界// 枚举老鼠团队人数x从0到n检查每种方案是否可行for(inti0;in;i){if(check(i))// 如果x位老鼠的方案满足所有人的希望ans;// 方案数加1}coutansendl;// 输出满足条件的选择方案总数return0;}【运行结果】4 0 3 3 2 2