思路:计算每个数组中每1相匹配的0的个数-->依次进行01转换比较每个1相匹配0的个数之和,取最大值。
int oz[210000][2]; int main(){ long time,i,n,j; int a[210000]={0}; int one,zero,k; long long sum,max,num; scanf("%d",&time); for(k=0;k<time;k++){ one=0; zero=0; scanf("%d\n",&n); for(i=0;i<n;i++){ scanf("%d",&a[i]); } one=0;zero=0; for(i=0,j=n-1;i<n&&j>=0;i++,j--){ if(a[i]){ one++; }if(!a[j]){ zero++; } //1,0的个数; oz[i][1]=one; oz[j][0]=zero; } //每个元素前的1的个数及后面0的个数; sum=0; for(i=0;i<n;i++){ if(a[i]==1){ sum+=oz[i][0]; //不转换前每个1后的0的个数之和; } } max=0; num=0; for(i=0;i<n;i++){ if(a[i]){ num=oz[i][1]-1-oz[i][0]; if(num>max){ max=num; } } else{ num=oz[i][0]-1-oz[i][1]; if(num>max){ max=num; } } } sum+=max; //原来的个数加上多出的; printf("%lld\n",sum); } return 0; }
标签:Binary,int,max,sum,个数,num,oz,Inversions From: https://www.cnblogs.com/Amon01/p/17033519.html