Subsequence Update

Subsequence UpdateCodeForces - 2063B 题目源地址输入621121323123313312423122252533235613366432输出1363118这题目的意思很明显只能进行一次操作要使范围内的值的和最小而且它的操作是反转并且交换的数量要一致那么要分成三块左边中间和右边显而易见操作只能是左边和中间或者是右边和中间重点是怎么操作实现#includebits/stdc.h#defineintlonglongusingnamespacestd;inta[100005];signedmain(){intt;cint;while(t--){intn,l,r;cinnlr;for(inti1;in;i){cina[i];}vectorintL,M,R;//分成三块for(inti1;il;i){L.push_back(a[i]);}for(intil;ir;i){M.push_back(a[i]);}for(intir1;in;i){R.push_back(a[i]);}intlen1min((int)M.size(),(int)L.size());//交换的数量限制可能是中间多或者是中间少交换只能选最小的intlen2min((int)M.size(),(int)R.size());sort(M.rbegin(),M.rend());//从大到小sort(L.begin(),L.end());//从小到大sort(R.begin(),R.end());vectorintpM(M.size()1,0);for(inti0;iM.size();i){pM[i1]pM[i]M[i];//前缀和,这样就提前处理好了方便}vectorintpL(L.size()1,0);for(inti0;iL.size();i){pL[i1]pL[i]L[i];}vectorintpR(R.size()1,0);for(inti0;iR.size();i){pR[i1]pR[i]R[i];}intzongpM[M.size()];//中间的和intminn1zong;for(inti0;ilen1;i){intsumzongpL[i]-pM[i];//pL[i]-pM[i]就是最后减少的值了minn1min(minn1,sum);//取最小的情况就是左边和中间的最优情况}intminn2zong;for(inti0;ilen2;i){intsumzongpR[i]-pM[i];minn2min(minn2,sum);}coutmin(minn1,minn2)endl;//最后左边和右边比较取最小}return0;}