签到题【牛客tracker 每日一题】
签到题
时间限制：1秒 空间限制：256M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
众所周知，签到题是一场比赛里难度最低的题目。 假定比赛中难度最低的题目的难度为x xx那么所有难度为x xx的题目都称之为"签到题"。
小 E 的题库里有n nn道题，第i ii道题的难度为a i a_iai。小 E 是良心出题人，他将在题库的n nn道题里选出m mm道题组成比赛题单，并使得题单里"签到题"的数目尽量多。
请输出"签到题"数量的最大值。
输入描述：
第一行输入两个整数n , m ( 1 ≤ m ≤ n ≤ 2 ∗ 10 5 ) n,m(1≤m≤n≤2∗10^5)n,m(1≤m≤n≤2∗105)。
第二行输入n nn个整数，第i ii个整数a i ( 1 ≤ a i ≤ n ) a_i(1≤a_i≤n)ai(1≤ai≤n)代表第i ii题的难度。
输出描述：
输出一个整数代表"签到题"数量的最大值。
示例1
输入：
5 3 1 2 2 2 3输出：
3示例2
输入：
6 5 2 2 1 2 2 1输出：
2示例3
输入：
6 2 1 1 4 5 1 4输出：
2解题思路
本题核心是排序+固定长度滑动窗口，通过题意转化将问题简化为窗口内频次统计问题。
题意转化：签到题是题单中难度最小的题目，要最大化签到题数量，等价于选择m道题，使其中最小难度的题目出现次数最多。最优策略是尽可能集中选取同一难度的题目，仅补充少量更高难度题目凑够m道。
算法步骤：
- 将难度数组降序排序，此时任意长度为m的连续子数组对应一种合法选法：子数组末尾元素是该选法的最小难度，它在窗口内的出现次数即为当前签到题数量。所有最优选法都对应降序数组中的一段连续子数组（选取若干高难度题+尽可能多的某一难度题），因此滑动窗口可以覆盖全部最优场景。
- 用计数数组维护窗口内各难度的频次，先初始化前m个元素的计数，初始答案为窗口末尾元素的出现次数。
- 滑动窗口遍历剩余元素：每次移除左端移出的元素、加入右端新元素，更新计数后，用当前窗口末尾元素的频次更新最大答案。
算法整体时间复杂度为O ( n log n ) O(n\log n)O(nlogn)，主要耗时为排序，滑动窗口仅需线性遍历，完美适配n ≤ 2 × 10 5 n \le 2\times10^5n≤2×105的数据约束。
总结
核心逻辑：降序排序后，固定长度窗口的末尾元素为当前最小难度，统计其在窗口内的最大出现次数即为答案。
关键操作：数组降序排序、固定窗口滑动、频次数组维护计数、实时更新最大值。
效率保障：排序为主要开销，滑动窗口无冗余运算，线性遍历即可求解，轻松处理二十万级数据。
代码简要说明
- 排序预处理：将难度数组从大到小排序，保证窗口内元素从左到右非递增，末尾元素始终是窗口最小值。
- 窗口初始化：统计前m个元素的各难度出现次数，将初始答案设为第m个元素（窗口末尾）的出现次数。
- 滑动遍历更新：从第m+1个元素开始逐个右移窗口，移除左端过期元素、加入当前新元素，更新计数后，用当前窗口末尾元素的频次更新最大答案。
- 输出结果：遍历完成后输出最大签到题数量。
代码内容
#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;constll maxn=2e5+10;ll a[maxn];ll cnt[maxn];intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n,m;cin>>n>>m;for(ll i=1;i<=n;i++)cin>>a[i];ll ans=0;sort(a+1,a+n+1,greater<ll>());for(ll i=1;i<=m;i++)cnt[a[i]]++;ans=cnt[a[m]];for(ll i=m+1;i<=n;i++){cnt[a[i-m]]--;cnt[a[i]]++;ans=max(ans,cnt[a[i]]);}cout<<ans<<endl;return0;}