企业官网建设流程全解析

Subsequence Update

CodeForces - 2063B 题目源地址

输入：

621121323123313312423122252533235613366432

输出：

1363118

这题目的意思很明显：

只能进行一次操作，要使范围内的值的和最小，而且它的操作是反转，并且交换的数量要一致，那么要分成三块，左边，中间和右边，显而易见，操作只能是左边和中间或者是右边和中间，重点是怎么操作实现

#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;inta[100005];signedmain(){intt;cin>>t;while(t--){intn,l,r;cin>>n>>l>>r;for(inti=1;i<=n;i++){cin>>a[i];}vector<int>L,M,R;//分成三块for(inti=1;i<l;i++){L.push_back(a[i]);}for(inti=l;i<=r;i++){M.push_back(a[i]);}for(inti=r+1;i<=n;i++){R.push_back(a[i]);}intlen1=min((int)M.size(),(int)L.size());//交换的数量限制，可能是中间多或者是中间少，交换只能选最小的intlen2=min((int)M.size(),(int)R.size());sort(M.rbegin(),M.rend());//从大到小sort(L.begin(),L.end());//从小到大sort(R.begin(),R.end());vector<int>pM(M.size()+1,0);for(inti=0;i<M.size();i++){pM[i+1]=pM[i]+M[i];//前缀和,这样就提前处理好了，方便}vector<int>pL(L.size()+1,0);for(inti=0;i<L.size();i++){pL[i+1]=pL[i]+L[i];}vector<int>pR(R.size()+1,0);for(inti=0;i<R.size();i++){pR[i+1]=pR[i]+R[i];}intzong=pM[M.size()];//中间的和intminn1=zong;for(inti=0;i<=len1;i++){intsum=zong+pL[i]-pM[i];//pL[i]-pM[i]就是最后减少的值了minn1=min(minn1,sum);//取最小的情况就是左边和中间的最优情况}intminn2=zong;for(inti=0;i<=len2;i++){intsum=zong+pR[i]-pM[i];minn2=min(minn2,sum);}cout<<min(minn1,minn2)<<endl;//最后左边和右边比较取最小}return0;}