首页 > 其他分享 >F. Binary Inversions

F. Binary Inversions

时间:2023-01-07 20:44:14浏览次数:43  
标签:Binary int max sum 个数 num oz Inversions

 

 思路:计算每个数组中每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

相关文章

  • [ABC264Ex] Perfect Binary Tree 题解
    [ABC264Ex]PerfectBinaryTreeSolution目录[ABC264Ex]PerfectBinaryTreeSolution更好的阅读体验戳此进入题面SolutionCodeUPD更好的阅读体验戳此进入题面存在一......
  • 在linux上安装mysql(二进制,binary)
    1.去https://dev.mysql.com/downloads/file/?id=514030下载mysql-5.7.40-linux-glibc2.12-x86_64.tar,将它scp到目标机器上。保存到/root/tools/下; 2.执行如下命令,将......
  • cf-1767C-Count Binary Strings(区间dp)
    题面https://codeforces.com/problemset/problem/1767/C下面展示带注释的ac代码在代码里解释思路Ac代码#include<bits/stdc++.h>#defineioios::sync_with_stdio(f......
  • [ABC264Ex] Perfect Binary Tree
    ProblemStatementWehavearootedtreewith$N$verticesnumbered$1,2,\dots,N$.ThetreeisrootedatVertex$1$,andtheparentofVertex$i\ge2$isVerte......
  • Perl Script to convert binary to hex
    Usage./bin2hex166_TurnItUpPhrVox_01_627a.mp31/*beginbinarydata:*/charbin_data[]=/*35065*/{0xFF,0xFB,0x90,0x04,0x00,0x00,0x00,0x00,0x00,0x00,0x0......
  • 消除警告:This TensorFlow binary is optimized with oneAPI Deep...
    AI入门级学习,大多数文章中优选推荐Keras,但是这个框架现在与TensorFlow简单绑定在一起(当然,你也可以选择另外的后端:如CNTK和Theano)。今天看一门老旧的图书,输入如下代码时出现......
  • Minimizing Go WebAssembly Binary Size
    MinimizingGoWebAssemblyBinarySizehttps://dev.bitolog.com/minimizing-go-webassembly-binary-size/ PostedonOctober9,2020byOmriCohenEstimatedrea......
  • LeetCode-Java-637. Average of Levels in Binary Tree
    题目Givenanon-emptybinarytree,returntheaveragevalueofthenodesoneachlevelintheformofanarray.Example1:Input:3/\920/\15......
  • codeforces 596 div2 p-binary(数位复杂度压缩)
    题目大意:已知: 同时  ,问k最少为多少。解题思路:首先,我们看到这里有2的n次方,我们考虑能不能从二进制表示下手,我们通过移位来表示:得到公式 ,很直接的想法是我们让k从小到大......
  • golang mysql查询textRows和binaryRows解惑
    1.问题之前写了一套统一mysql返回数据的解析库:rows,err:=ms.dbInst.Query(s,args...) //执行SQL语句,比如select*fromusersiferr!=nil{panic(err)}......