Swap to Gather-----
C - 烟销日出不见人
问题陈述
给定一个长度为 NN 的字符串 SS,由 0 和 1 组成。保证 SS 至少包含一个 1。
您可以执行以下操作任意次数(可能为零):
- 选择一个整数 ii (1≤i≤N−11≤i≤N−1),并交换 SS 的第 ii 个和第 (i+1)(i+1) 个字符。
找出使所有 1 连续所需的最小操作次数。
在这里,只有当存在整数 ll 和 rr (1≤l≤r≤N1≤l≤r≤N) 时,所有 1 被称为连续,且 ii 的第 1 个字符为 SS 当且仅当 l≤i≤rl≤i≤r,否则为 0。
约束条件
- 2≤N≤5×1052≤N≤5×105
- NN 是一个整数。
- SS 是一个长度为 NN 的字符串,由
0和1组成。 - SS 至少包含一个
1。
输入
输入通过标准输入以以下格式给出:
NN SS
输出
打印答案。
示例 1
| Inputcopy | Outputcopy |
|---|---|
7 0101001 | 3 |
例如,以下三个操作使所有 1 连续:
- 选择 i=2i=2 并交换第 2 个和第 3 个字符。然后,S=S=
0011001。 - 选择 i=6i=6 并交换第 6 个和第 7 个字符。然后,S=S=
0011010。 - 选择 i=5i=5 并交换第 5 个和第 6 个字符。然后,S=S=
0011100。
不可能在两次或更少的交换中做到这一点,因此答案是 33。
示例 2
| Inputcopy | Outputcopy |
|---|---|
3 100 | 0 |
所有 1 已经是连续的,因此不需要交换。
示例 3
| Inputcopy | Outputcopy |
|---|---|
10 0101001001 | 7 |
思路:
假设最左端在第一个点,移动次数最小;
然后从此点循环到最右点-1的个数点,
每循环一次看有多少点应该向右移,有多少点应该向左移,但他们都向左移动了,所以要计算
代码:
//假设最左端在第一个点,移动次数最小;
//然后从此点循环到最右点-1的个数点,
// 每循环一次看有多少点应该向右移,有多少点应该向左移,但他们都向左移动了,所以要计算
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
char a[600010];
int b[600010];
int n;
long long sum = 0, max = 0, h = 0, q, i, zong = 0,y=0;
int main() {scanf("%d", &n);for ( i = 0;i < n;i++) {do{scanf("%c", &a[i]);} while (a[i] != '1' && a[i] != '0');}for ( i = 0;i < n;i++) {if (a[i] == '1'&&h==0) {q = i;b[y++] = i;max += i -q -h;h++;}//第一个点else if (a[i] == '1') {b[y++] = i;max+= i -q -h;h++;}//后面的点到据第一个点的h距离}sum = max;for ( i = q+1;i <= b[y-1] - h+1 && zong<y;i++) {while (i+zong >b[zong]&&zong<y ) {zong++;}//有几个要向右移动max = max + 2 * zong - h;//zong个要向右移动,h-zong个不要向右移动但移动了(减去)sum = sum < max ? sum : max;}printf("%lld\n", sum);return 0;
}
相关文章:
Swap to Gather-----
C - 烟销日出不见人 问题陈述 给定一个长度为 NN 的字符串 SS,由 0 和 1 组成。保证 SS 至少包含一个 1。 您可以执行以下操作任意次数(可能为零): 选择一个整数 ii (1≤i≤N−11≤i≤N−1),并交换 SS 的第 ii 个和…...
使用DeepSeek+本地知识库,尝试从0到1搭建高度定制化工作流(自动化篇)
7.5. 配图生成 目的:由于小红书发布文章要求图文格式,因此在生成文案的基础上,我们还需要生成图文搭配文案进行发布。 原实现思路: 起初我打算使用deepseek的文生图模型Janus进行本地部署生成,参考博客:De…...
Python 函数式编程全攻略:从理论到实战的深度解析
本文深入剖析 Python 函数式编程,详细讲解其概念、核心特性(迭代器、生成器等)、内置函数及相关模块(itertools、functools ),结合丰富示例与直观图表,助力读者全面掌握函数式编程技巧ÿ…...
Ollama 在 LangChain 中的使用
文章目录 一、langChain 介绍二、环境安装1.依赖库安装2.下载模型 三、基本使用示例1.使用 ChatPromptTemplate 进行对话2.流式输出3.工具调用4.多模态模型调用 四、进阶使用1.使用 ConversationChain 进行对话2.自定义提示模板3.构建一个简单的 RAG 问答系统 五、遇到问题与解…...
使用apt-rdepends制作软件离线deb安装包
使用apt-rdepends制作软件离线deb安装包 除基础软件外,还要获取软件依赖包。 依赖包工具安装 apt-get install apt-rdependsapt-rdepends工具使用 使用apt-rdepends工具,递归方式分析软件依赖,下载软件包本体,和依赖包。制作时…...
根据POD名称生成 三部曲:get、describe、log、exec
#!/bin/bash# 定义颜色变量 RED\033[0;31m GREEN\033[0;32m YELLOW\033[0;33m NC\033[0m # No Color# 检查是否传入 Pod 名称作为参数 if [ -z "$1" ]; then# 如果没有传参,则提示用户输入 Pod 名称echo -e "${YELLOW}Please enter the Pod name:${…...
SQL sever数据导入导出实验
1.创建数据库TCP-H (1)右键“数据库”,点击“新建数据库”即可 (2)用sql语言创建,此处以创建数据库DB_test为例,代码如下: use master;go--检查在当前服务器系统中的所有数据里面…...
python环境的yolov11.rknn物体检测
1.首先是我手里生成的一个yolo11的.rknn模型: 2.比对一下yolov5的模型: 2.1 yolov5模型的后期处理: outputs rknn.inference(inputs[img2], data_format[nhwc])np.save(./onnx_yolov5_0.npy, outputs[0])np.save(./onnx_yolov5_1.npy, outpu…...
I2C、SPI、UART
I2C:串口通信,同步,半双工,双线(数据线SDA时钟线SCL),最大距离1米到几米 SPI(串行外设接口):串口通信,同步,全双工,四线&…...
如何监控和优化 MySQL 中的慢 SQL
如何监控和优化 MySQL 中的慢 SQL 前言一、什么是慢 SQL?二、如何监控慢 SQL?1. 启用慢查询日志启用方法:日志内容: 2. 使用 mysqldumpslow 分析日志 三、如何分析慢 SQL?1. 使用 EXPLAIN 分析执行计划使用方法&#x…...
13-二叉树最小深度-深度优先(DFS)
一、定义 什么是二叉树的最小深度? 二叉树的最小深度是指从根节点到最近的叶子节点的最短路径上的节点数。叶子节点是指没有子节点的节点。 举个例子: 1/ \2 3/ 4 这棵树的最小深度是 2,因为从根节点 1 到叶子节点 3 的路径最短&#x…...
51单片机入门_10_数码管动态显示(数字的使用;简单动态显示;指定值的数码管动态显示)
接上篇的数码管静态显示,以下是接上篇介绍到的动态显示的原理。 动态显示的特点是将所有位数码管的段选线并联在一起,由位选线控制是哪一位数码管有效。选亮数码管采用动态扫描显示。所谓动态扫描显示即轮流向各位数码管送出字形码和相应的位选ÿ…...
代码补全『三重奏』:EverEdit如何用上下文识别+语法感知+智能片段重构你的编码效率!
1 代码自动完成 1.1 应用场景 在编辑文档时,为了提高编辑效率,编辑器一般都会带有自动完成功能,比如:输入括号时自动补全另一半,输入文字时,自动补全剩下的部分。 1.2 使用方法 1.2.1 自动缩进 单击主菜…...
电脑系统损坏,备份文件
一、工具准备 1.U盘:8G以上就够用,注意会格式化U盘,提前备份U盘内容 2.电脑:下载Windows系统并进行启动盘制作 二、Windows启动盘制作 1.微软官网下载启动盘制作工具微软官网下载启动盘制作工具https://www.microsoft.com/zh-c…...
Token Statistics Transformer:线性注意力革命,重新定义Transformer效率天花板
“TOKEN STATISTICS TRANSFORMER: LINEAR-TIME ATTENTION VIA VARIATIONAL RATE REDUCTION” 由Ziyang Wu等人撰写。文章提出一种新型Transformer注意力算子,通过对最大编码率降低( M C R 2 MCR^{2} MCR2)目标的变分形式进行展开优化得到&…...
Django 5实用指南(二)项目结构与管理
2.1 Django5项目结构概述 当你创建一个新的 Django 项目时,Django 会自动生成一个默认的项目结构。这个结构是根据 Django 的最佳实践来设计的,以便开发者能够清晰地管理和维护项目中的各种组件。理解并管理好这些文件和目录结构是 Django 开发的基础。…...
JAVA监听器(学习自用)
一、什么是监听器 servlet监听器是一种特殊的接口,用于监听特定的事件(如请求创建和销毁、会话创建和销毁、上下文的初始化和销毁)。 当Web应用程序中反生特定事件时,Servlet容器就会自动调用监听器中相应的方法来处理这些事件。…...
Ubuntu下mysql主从复制搭建
本文介绍mysql 8.4主从集群的搭建,从单个机器安装到集群的配置,整体走了一遍,希望对大家有帮助。mysql 8.4和之前的版本命令上有些变化,大家用来参考。 0、环境 ubuntu: 22.04mysql:8.4 1、安装mysql 1…...
VirtualBox 中使用 桥接网卡 并设置 MAC 地址
在 VirtualBox 中使用 桥接网卡 并设置 MAC 地址,可以按照以下步骤操作: 步骤 1:设置桥接网卡 打开 VirtualBox,选择你的虚拟机,点击 “设置” (Settings)。进入 “网络” (Network) 选项卡。在 “适配器 1” (Adapt…...
Ubuntu 20 掉显卡驱动的解决办法
目录 问题背景解决办法Step1:首先查看当前linux内核Step2:重启Step3:进入ubuntu advanced (即高级选项)Step4:查看有哪些linux内核Step5:如果滚回老板kernel还是没有驱动,就找到驱动…...
Java如何权衡是使用无序的数组还是有序的数组
在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...
Rust 异步编程
Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...
Python 包管理器 uv 介绍
Python 包管理器 uv 全面介绍 uv 是由 Astral(热门工具 Ruff 的开发者)推出的下一代高性能 Python 包管理器和构建工具,用 Rust 编写。它旨在解决传统工具(如 pip、virtualenv、pip-tools)的性能瓶颈,同时…...
VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP
编辑-虚拟网络编辑器-更改设置 选择桥接模式,然后找到相应的网卡(可以查看自己本机的网络连接) windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置,选择刚才配置的桥接模式 静态ip设置: 我用的ubuntu24桌…...
day36-多路IO复用
一、基本概念 (服务器多客户端模型) 定义:单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力 作用:应用程序通常需要处理来自多条事件流中的事件,比如我现在用的电脑,需要同时处理键盘鼠标…...
android RelativeLayout布局
<?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"match_parent"android:gravity&…...
k8s从入门到放弃之HPA控制器
k8s从入门到放弃之HPA控制器 Kubernetes中的Horizontal Pod Autoscaler (HPA)控制器是一种用于自动扩展部署、副本集或复制控制器中Pod数量的机制。它可以根据观察到的CPU利用率(或其他自定义指标)来调整这些对象的规模,从而帮助应用程序在负…...
动态规划-1035.不相交的线-力扣(LeetCode)
一、题目解析 光看题目要求和例图,感觉这题好麻烦,直线不能相交啊,每个数字只属于一条连线啊等等,但我们结合题目所给的信息和例图的内容,这不就是最长公共子序列吗?,我们把最长公共子序列连线起…...
Java中HashMap底层原理深度解析:从数据结构到红黑树优化
一、HashMap概述与核心特性 HashMap作为Java集合框架中最常用的数据结构之一,是基于哈希表的Map接口非同步实现。它允许使用null键和null值(但只能有一个null键),并且不保证映射顺序的恒久不变。与Hashtable相比,Hash…...
免费批量Markdown转Word工具
免费批量Markdown转Word工具 一款简单易用的批量Markdown文档转换工具,支持将多个Markdown文件一键转换为Word文档。完全免费,无需安装,解压即用! 官方网站 访问官方展示页面了解更多信息:http://mutou888.com/pro…...
