Harder ProblemCodeForces - 2044D 题目源地址作者脑子转不过来了就是写不出来难以想到无法形容。我写的时候想了好久现在看了题解也还是不太懂我只能写一下这个说不定过程中就想通了呢(现版本我把解题的步骤分点好了不然一坨不太好看)题意数组b [ i ] b[i]b[i]前面的数包括进来得到的众数要是a [ i ] a[i]a[i]题解#includebits/stdc.h#defineintlonglongusingnamespacestd;inta[200005];intb[200005];signedmain(){intt;cint;while(t--){intn;cinn;setints;//选用set是因为它取里面的数和删除比较方便//当然用队列也是可以的vector的话不能使用count,比较麻烦for(inti1;in;i){cina[i];s.insert(i);}for(inti1;in;i){if(s.count(a[i])){b[i]a[i];s.erase(a[i]);}else{b[i]*s.begin();s.erase(b[i]);}}intf0;for(inti1;in;i){if(f)cout ;//输出的格式控制coutb[i];}coutendl;}return0;}紧急插播上面的我借鉴了AI来理解我后面又请教了我的同学我感觉挺好的我来讲解一下那个版本其实差是差不多的但是我感觉好理解神了#includebits/stdc.h#defineintlonglongusingnamespacestd;boolvis[200005];//标记是不是a[i]inta[200005];signedmain(){intt;cint;while(t--){intn;cinn;memset(vis,false,sizeofvis);//初始化不要忘了queueintq;vectorintv;//存入b[i]统一输出for(inti1;in;i){cina[i];vis[a[i]]true;//标记}for(inti1;in;i){if(!vis[i]){q.push(i);//不会影响到前缀众数的数统一放}}for(inti1;in;i){if(vis[a[i]]){v.push_back(a[i]);vis[a[i]]false;用过了要标记,不要重复}else{intbq.front();q.pop();v.push_back(b);}}intf0;for(inti0;iv.size();i){if(f)cout ;coutv[i];}coutendl;}return0;}解释题目中有1 b [ i ] n 1b[i]n1b[i]n想要每个前缀的众数都有可能那就可以每个都只放一个不然会打破平衡这样只用考虑前缀的众数是a [ i ] a[i]a[i]了刚好都排满。遍历a [ i ] a[i]a[i],标记已经有的有的直接b [ i ] a [ i ] b[i]a[i]b[i]a[i],这样前缀的众数肯定没问题没有标记的随便填但填了还是要删了不然会打破平衡。
