数列最小次数翻转

牛妹爱数列

https://ac.nowcoder.com/acm/contest/6885/D

问题描述

他手里有一个长度为n的序列a,保证它是一个01序列,并执行以下两种操作:
1.单点修改:将位置x上的数翻转(0变1,1变0);
2.前缀修改:将位置1~x上的数翻转(每个数都0变1,1变0)。
他现在想要最小化翻转次数,使得数列上的所有数都变为0。

输入输出

第一行,输入一个数n。
第二行,输入n个数,第i个数表示aia_iai​。

输出最小翻转次数。

代码

import java.util.*;
public class Main{

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = scan.nextInt();
        System.out.println(solution(arr));
    }

    private static int solution(int[] arr) {
        int count = 0;
        boolean flag = true;
       // 从后往前
        for (int i = arr.length-1; i >= 0; i--) {
            if (flag && arr[i] == 0 || !flag && arr[i] == 1) continue;
            else if (flag && arr[i] == 1) {  // 从0到1
                if (i == 0 || arr[i - 1] == 0) count++;  // 下一个又变回0
                else {
                    flag = !flag;
                    count++;
                }
            } else {   // 从1到0
                if (i == 0 || arr[i - 1] == 1) count++;  // 下一个又变回1
                else {
                    flag = !flag;
                    count++;
                }
            }
        }
        return count;
    }
}
全部评论

相关推荐

昨天 10:17
仰恩大学 营销
bg双非,被挂了
投递拼多多集团-PDD等公司10个岗位
点赞 评论 收藏
分享
码农索隆:竞争压力小,就你一个不用卷
点赞 评论 收藏
分享
醉蟀:你不干有的是人干
点赞 评论 收藏
分享
来个厂收我吧:首先,市场侧求职我不是很懂。 但是,如果hr把这份简历给我,我会觉得求职人不适合做产品经理。 问题点: 1,简历的字体格式不统一,排版不尽如人意 2,重点不突出,建议参考star法则写个人经历 3,印尼官方货币名称为印度尼西亚卢比(IDR),且GMV690000印尼盾换算为305人民币,总成交额不高。 4,右上角的意向职位在发给其他公司时记得删除。 5,你所有的经历都是新媒体运营,但是你要投市场营销岗位,jd和简历不匹配,建议用AI+提示词,参照多个jd改一下经历内容。 修改建议: 1,统一字体(中文:思源黑体或微软雅黑,英文数字:time new romans),在word中通过表格进行排版(b站学) 2,校招个人经历权重:实习经历=创业经历(大创另算)>项目经历>实训经历>校园经历 3,请将项目经历时间顺序改为倒序,最新的放最上方。 4,求职方向不同,简历文字描述侧重点也需要不同。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务