CDOJ490UESTC490SwapGame

作者： | 来源：互联网 | 2023-09-23 18:42

题意：有两种颜色的小球形成环，求最小交互次数使球相连。题解：先解决另一个简单的问题，如果是一个链，把红球标记为1，蓝球标记为0，要排成升序需要多少次交换呢？答案是逆序对总数，原因是

题意：有两种颜色的小球形成环，求最小交互次数使球相连。

题解：先解决另一个简单的问题，如果是一个链，把红球标记为1，蓝球标记为0，要排成升序需要多少次交换呢？答案是逆序对总数，原因是一次交互最多消除一个逆序对，而且有策略可以保证每次消除一个逆序对。要解决这个问题，需要做一些变通。看蓝球，因为是环，为了使交换次数最小，前半段的蓝球应该往前靠，所以在后半段的蓝球应该往后靠。那么就把原序列划分成两半，前面一段记红球为1，蓝球为0，后面一段记蓝球为1，红球为0，然后分别计算逆序对数，就可以求出以0位置前为中心的逆序数。然后在枚举中心的位置，枚举的时候，可以在O(1)时间计算出新的逆序值，具体方法是只考虑端点处的小球对左右区间逆序值的影响。技术分享

记左区间长度为b1，把中心移动到b1+i球的后面，那么b1+i位置的球会加入左区间，i号球则加入到右区间，当b1+i号球是R的时候，它对左右两边的逆序值都是没有影响的，(对于右区间，R是0，对于左区间，R是1)，当它是B的时候，对于右区间，逆序对总数减少了原来右区间中0的个数，对于左区间，增加了i移动之后1的个数。对于i的移动，类似地讨论一下。

#include
#include
#include
#include
#include<set>
#include
#include
#include
using namespace std;
typedef long long ll;
//#define local



const int maxn = 1e5+500;

int C[2];

char str[maxn];

int main()
{
#ifdef local
    freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
#endif // local
    int T;
    scanf("%d",&T);getchar();
    for(int k = 1; k <= T; k++){
        printf("Case #%d: ",k);
        gets(str);
        memset(C,0,sizeof(C));
        int len = strlen(str);
        int invSum  = 0;
        int b1 = len>>1,b2 = len - b1;
        for(int i = 0; i ) {
            if(str[i] == ‘R‘) { C[0]++;}
            else { invSum += C[0]; }
        }
        for(int i = b1; i ) {
            if(str[i] == ‘B‘) {  C[1]++;}
            else { invSum += C[1]; }
        }

        int best = invSum;
        //printf("%d\n",best);
        for(int i = 0; i ){
            int t = (b1+i)%len;
            if(str[t] == ‘B‘) { invSum -= b2-C[1]; invSum += C[0]- (str[i] == ‘R‘); }
            if(str[i] == ‘R‘ ) { invSum -= b1-C[0]; invSum += C[1] - (str[t] == ‘B‘); }
            if(str[t] == ‘B‘) C[1]--;
            else C[0]++;
            if(str[i] == ‘R‘) C[0]--;
            else C[1]++;
            best = min(invSum,best);
        }
        printf("%d\n",best);
    }
    return 0;
}

CDOJ 490 UESTC 490 Swap Game

推荐阅读

io
UVALive 8201 - BBP 公式计算圆周率

在1995年，Simon Plouffe 发现了一种特殊的求和方法来表示某些常数。两年后，Bailey 和 Borwein 在他们的论文中发表了这一发现，这种方法被命名为 Bailey-Borwein-Plouffe (BBP) 公式。该问题要求计算圆周率 π 的第 n 个十六进制数字。 ... [详细]

蜡笔小新 2024-11-21 18:32:57
sum
HDU 6116 路径计数优化

本文探讨了使用普通生成函数和指数生成函数解决组合与排列问题的方法，特别是在处理特定路径计数问题时的应用。文章通过详细分析和代码实现，展示了如何高效地计算在给定条件下不相邻相同元素的排列数量。 ... [详细]

蜡笔小新 2024-11-22 13:11:20
io
深入解析Unity3D游戏开发中的音频播放技术

在游戏开发中，音频播放是提升玩家沉浸感的关键因素之一。本文将探讨如何在Unity3D中高效地管理和播放不同类型的游戏音频，包括背景音乐和效果音效，并介绍实现这些功能的具体步骤。 ... [详细]

蜡笔小新 2024-11-22 21:05:22
js
深入理解C++中的自定义String类实现

本文探讨了一种常见的C++面试题目——实现自己的String类。通过此过程，不仅能够检验开发者对C++基础知识的掌握程度，还能加深对其高级特性的理解。文章详细介绍了如何实现基本的功能，如构造函数、析构函数、拷贝构造函数及赋值运算符重载等。 ... [详细]

蜡笔小新 2024-11-22 19:21:22
js
CentOS 服务器自定义密码策略

随着Linux操作系统的广泛使用，确保用户账户及系统安全变得尤为重要。用户密码的复杂性直接关系到系统的整体安全性。本文将详细介绍如何在CentOS服务器上自定义密码规则，以增强系统的安全性。 ... [详细]

蜡笔小新 2024-11-22 19:15:42
js
探索Java 11中的ZGC垃圾收集器

Java 11引入了一种新的垃圾收集器——ZGC，由Oracle公司研发，旨在支持TB级别的内存容量，并保证极低的暂停时间。本文将探讨ZGC的开发背景、技术特点及其潜在的应用前景。 ... [详细]

蜡笔小新 2024-11-22 13:36:53
js
在Notepad++中配置Markdown语法高亮及实时预览功能

本文详细介绍了如何在Notepad++中配置Markdown语法高亮和实时预览功能，包括必要的插件安装和设置步骤。 ... [详细]

蜡笔小新 2024-11-22 13:03:49
js
解决映射文件中重复属性字段问题

探讨如何在映射文件中处理重复的属性字段，以避免数据操作时出现错误。 ... [详细]

蜡笔小新 2024-11-22 11:48:50
io
网络流24题——试题库问题

题目描述：假设一个试题库中有n道试题。每道试题都标明了所属类别。同一道题可能有多个类别属性。现要从题库中抽取m道题组成试卷。并要求试卷包含指定类型的试题。试设计一个满足要求的组卷算 ... [详细]

蜡笔小新 2024-11-22 11:33:55
js
利用无代码平台实现高效业务应用开发

随着市场环境的变化加速，全球企业都在探索更为敏捷的应用开发模式，以便快速响应新兴的商业机遇。然而，传统的软件开发方式不仅成本高昂，而且耗时较长，这往往导致IT与业务部门之间的合作障碍，进而影响项目的成功。本文将探讨如何通过无代码开发平台解决这些问题。 ... [详细]

蜡笔小新 2024-11-22 11:09:21
io
为何Compose与Swarm之后仍有Kubernetes的诞生？

探讨在已有Compose和Swarm的情况下，Kubernetes是如何以其独特的设计理念和技术优势脱颖而出，成为容器编排领域的领航者。 ... [详细]

蜡笔小新 2024-11-22 09:26:11
js
使用 Python3 和 sqlacodegen 从现有数据库生成 ORM Model 文件

本文介绍了如何通过安装 sqlacodegen 和 pymysql 来根据现有的 MySQL 数据库自动生成 ORM 的模型文件（model.py）。此方法适用于需要快速搭建项目模型层的情况。 ... [详细]

蜡笔小新 2024-11-22 01:13:04
js
程序员的精神世界与职业追求

本文探讨了程序员这一职业的本质，认为他们是专注于问题解决的专业人士。文章深入分析了他们的日常工作状态、个人品质以及面对挑战时的态度，强调了编程不仅是一项技术活动，更是个人成长和精神修炼的过程。 ... [详细]

蜡笔小新 2024-11-21 18:56:08
io
SIP基础概览

本文介绍了SIP（Session Initiation Protocol，会话发起协议）的基本概念、功能、消息格式及其实现机制。SIP是一种在IP网络上用于建立、管理和终止多媒体通信会话的应用层协议。 ... [详细]

蜡笔小新 2024-11-21 17:42:08
io
二维码的实现与应用

本文介绍了二维码的基本概念、分类及其优缺点，并详细描述了如何使用Java编程语言结合第三方库（如ZXing和qrcode.jar）来实现二维码的生成与解析。 ... [详细]

蜡笔小新 2024-11-21 17:10:15

Tags | 热门标签

RankList | 热门文章