企业官网建设流程全解析

网络公司的手机网站,网站安全建设目标,上海建设工程招投标网站,明会红网站题目描述 本题模拟了一个裁员队列的过程。 NNN 个申请人围成一个圆圈#xff0c;从编号 111 开始逆时针编号到 NNN 。每天#xff0c;两位官员分别从编号 111#xff08;逆时针方向#xff09;和编号 NNN#xff08;顺时针方向#xff09;开始数人。一位官员每次数 kkk 个…题目描述本题模拟了一个裁员队列的过程。NNN个申请人围成一个圆圈从编号111开始逆时针编号到NNN。每天两位官员分别从编号111逆时针方向和编号NNN顺时针方向开始数人。一位官员每次数kkk个有效申请人跳过已被选中的人另一位官员每次数mmm个有效申请人。被选中的两个人将同时离开圆圈如果两人选中同一人则该人仅离开一次。重复此过程直到所有人都被选中。要求按离开的顺序输出编号每对编号或单独编号占333字符宽用逗号分隔末尾不加逗号。输入格式多组数据每组一行三个整数N,k,mN, k, mN,k,m满足k,m0,0N20k, m 0, 0 N 20k,m0,0N20。以0 0 0结束输入。输出格式对每组数据输出一行表示离开顺序格式如上所述。样例输入10 4 3 0 0 0样例输出4 8, 9 5, 3 1, 2 6, 10, 7解题思路本题是一个典型的约瑟夫环问题的变种区别在于有两个方向同时进行数人且每次选中的两人同时离开。由于N20N 20N20数据规模很小可以直接用数组模拟整个过程。关键点分析模拟圆圈使用数组circle存储当前还在圈中的人的编号被选中的人将其值置为000表示离开。数人逻辑逆时针方向从当前位置right开始数kkk个有效的人顺时针方向从当前位置left开始数mmm个有效的人由于选中的人会离开所以数人时需要跳过值为000的位置。同时离开如果两个官员选中同一个人只输出一次并且只将nnn减少111否则分别输出并减少222。输出格式使用setw(3)控制输出宽度为333字符用逗号分隔不同对或单独编号注意末尾没有逗号。算法步骤读入N,k,mN, k, mN,k,m若全为000则结束。初始化数组circle为111到NNN。设置两个指针right和left分别表示逆时针和顺时针的起始位置。当还有人未离开时从right开始逆时针数kkk个有效位置更新right为选中位置。从left开始顺时针数mmm个有效位置更新left为选中位置。输出circle[right]占333字符将其置000剩余人数减一。如果right ! left输出circle[left]占333字符将其置000剩余人数再减一。如果还有人剩余输出逗号。输出换行处理下一组数据。代码实现// The Dole Queue// UVa ID: 133// Verdict: Accepted// Submission Date: 2015-12-13// UVa Run Time: 0.000s//// 版权所有C2015邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intn,k,m;vectorintcircle;// count off in counter-clockwise and return the index of target.intfindCCW(intright,intnumber){for(intiright;icircle.size();i)if(circle[i]0((--number)0))returni;while(true){for(inti0;icircle.size();i)if(circle[i]0((--number)0))returni;}}// count off in clockwise and return the index of target.intfindCW(intleft,intnumber){for(intileft;i0;i--)if(circle[i]0((--number)0))returni;while(true){for(inticircle.size()-1;i0;i--)if(circle[i]0((--number)0))returni;}}intmain(){setfill( );while(cinnkm,n||k||m){circle.clear();for(inti1;in;i)circle.push_back(i);intright0,leftn-1;while(n0){rightfindCCW(right,k);leftfindCW(left,m);coutsetw(3)circle[right];circle[right]0;n--;if(right!left){coutsetw(3)circle[left];circle[left]0;n--;}if(n0)cout,;}coutendl;}return0;}复杂度分析时间复杂度每次数人最多遍历整个数组总复杂度为O(N2)O(N^2)O(N2)由于N≤20N \leq 20N≤20完全可行。空间复杂度O(N)O(N)O(N)。总结本题是一个有趣的模拟题关键在于理解两个方向同时数人的逻辑并处理好选中同一人的特殊情况。输出格式要求较严格注意使用setw控制宽度和逗号的位置即可。