P8188 [USACO22FEB] Email Filing S题目描述Farmer John 在整理他的收件箱时落后了。他的屏幕布局如下屏幕左侧是文件夹的垂直列表右侧是邮件的垂直列表。总共有MMM个文件夹编号为1…M1 \ldots M1…M1≤M≤1041 \leq M \leq 10^41≤M≤104。他的收件箱目前包含NNN封邮件编号为1…N1 \ldots N1…N1≤N≤1051 \leq N \leq 10^51≤N≤105第iii封邮件需要归档到文件夹fif_ifi​1≤fi≤M1 \leq f_i \leq M1≤fi​≤M。FJ 的屏幕很小因此他一次只能查看KKK个文件夹和KKK封邮件1≤K≤min⁡(N,M)1 \leq K \leq \min(N, M)1≤K≤min(N,M)。初始时他的屏幕显示左侧的文件夹1…K1 \ldots K1…K和右侧的邮件1…K1 \ldots K1…K。为了访问其他文件夹和邮件他需要滚动这些列表。例如如果他在文件夹列表中向下滚动一个位置屏幕将显示文件夹2…K12 \ldots K12…K1再向下滚动一个位置则显示文件夹3…K23 \ldots K23…K2。当 FJ 将一封邮件拖入文件夹时该邮件会从邮件列表中消失其后的邮件会向前移动一个位置。例如如果当前显示的邮件是1,2,3,4,51, 2, 3, 4, 51,2,3,4,5而 FJ 将邮件333拖入其对应的文件夹邮件列表将显示1,2,4,5,61, 2, 4, 5, 61,2,4,5,6。FJ 只能将邮件拖入其需要归档的文件夹。不幸的是FJ 的鼠标滚轮坏了他只能向下滚动不能向上滚动。唯一能实现类似向上滚动的效果是当他查看邮件列表的最后KKK封邮件时如果他归档了其中一封邮件邮件列表将再次显示尚未归档的最后KKK封邮件从而将最上面的邮件向上滚动一个位置。如果剩余的邮件少于KKK封则显示所有剩余的邮件。请帮助 FJ 判断是否能够归档所有邮件。输入格式输入的第一行包含TTT1≤T≤101 \leq T \leq 101≤T≤10表示输入中的子用例数量所有子用例都必须正确解决才能解决整个输入用例。接下来的TTT行是每个子用例的输入。对于每个子用例第一行包含MMM、NNN和KKK。第二行包含f1⋯fNf_1 \cdots f_Nf1​⋯fN​。保证所有子用例的MMM之和不超过10410^4104所有子用例的NNN之和不超过10510^5105。输出格式输出TTT行每行包含YES或NO表示 FJ 是否能够成功归档所有邮件。输入输出样例 #1输入 #16 5 5 1 1 2 3 4 5 5 5 1 1 2 3 5 4 5 5 1 1 2 4 5 3 5 5 2 1 2 4 5 3 3 10 2 1 3 2 1 3 2 1 3 2 1 3 10 1 1 3 2 1 3 2 1 3 2 1输出 #1YES YES NO YES YES NO说明/提示在输入 2-10 中所有子用例的MMM之和不超过10310^3103。在输入 11-12 中没有额外限制。C实现#includebits/stdc.husingnamespacestd;typedefpairint,intpii;#definempmake_pair#definefifirst#definesesecondconstintN1e55;intT,m,n,k,cnt[N],a[N],vis[N];intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);for(cinT;T;T--){cinmnk;for(inti1;in;i)cnt[i]0,vis[i]0;dequeintl;// 存储被跳过的邮件priority_queuepii,vectorpii,greaterpiiq;for(inti1;in;i){cina[i];if(ik)q.push(mp(a[i],i));cnt[a[i]];}intfl1,frk,fold1;while(q.size()||l.size()){while(!cnt[fold]foldm-k1)fold;if(q.size()q.top().fifoldq.top().fifoldk-1){--cnt[q.top().fi];vis[q.top().se]true;// 记录已经放好的邮件q.pop();if(frn){fr;q.push(mp(a[fr],fr));}}elseif(frn){// 邮件窗口没有滑到底时模拟补位fl,fr;q.push(mp(a[fr],fr));l.push_back(a[fl-1]);// 记录跳过的邮件}elseif((int)q.size()kl.size()){// 邮件窗口滑到底之后模拟补位--fl;q.push(mp(l.back(),fl));l.pop_back();}elsebreak;while(q.size()q.top().sefl)q.pop();// 保证堆顶的邮件是没有被跳过的while(vis[fl])fl;// 保证 fl 位置的邮件是没有放好的}if(q.size())coutNO\n;elsecoutYES\n;}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容