`
tiankonguse
  • 浏览: 16134 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
社区版块
存档分类
最新评论

关于 double sort 这道题的思考

阅读更多

声明

   笔者最近意外的发现 笔者的个人网站 http://tiankonguse.com/ 的很多文章被其它网站转载,但是转载时未声明文章来源或参考自 http://tiankonguse.com/ 网站,因此,笔者添加此条声明。

    郑重声明:这篇记录《关于 double sort 这道题的思考》转载自 http://tiankonguse.com/ 的这条记录:http://tiankonguse.com/record/record.php?id=651

 

前言

 

前言的前言

昨天本来写好了这篇记录,可恨中间我出去打了一个电话,回来继续写,写完我想到可能session已经失效,所以我新打开一个页面,登录,然后在这个页面提交。返回了提交成功的标签,但是跳转到那篇文章时提示不存在。这个,我不能再忍受了,于是自己做了一个自动保存的功能。

 

首先今天写的内容将会简短,因为昨天写的好久好久,结果自动保存功能还没有实现。不过现在,时刻都在自动保存着,再也不用担心这个问题了。

首先声明这篇记录不是解题报告,只是一场我的大脑里思路的旅行。

 

前几天学弟学妹们有一场比赛,学弟邀请我作为技术支持者去帮忙,在那个过程中我看了几道题。

其中有两道题正常比赛没有其他人提交,于是我研究了一下。

研究的第一道就一个暴力dfs就可以过,只是可能正常比赛没人看懂题意,我看了好几个小时才看懂的。

第二道就是 double sort。

 

正文

题意

 

什么是 double sort 呢?

就以题目中的讲解例子来说说吧。

题目说对于一组数 [5; 4; 3; 2; 1], 如果只可以交换相邻的数字,要使这组数达到升序至少需要 10 步。

这个很好理解,假设一个数字要和左面的数字交换,那只有一种情况。

但是对于两组数 [5,5; 4,4; 3,3; 2,2; 1,1] 来说,也是只能交换相邻的数字。这是一个数字和左面的数字交换时就有两种情况了。

比如对于 4 可以和 第一个5交换,也可以和第二个5交换。

目标是使这两组数字达到升序。题意还说这个例子的答案是 15 ,不是 20.

 

然后,没然后了。

 

错误的题意

看完上面的题意,我有一个疑问:难道真的是要排成 [5,5; 4,4; 3,3; 2,2; 1,1] 的样子吗? 15 步可能吗?

于是我猜测可能是达到每组升序即可,比如 [4,5; 4,5; 2,3; 2,3; 1,1], 这样第一组是 [4; 4; 2; 2; 1], 第二组书[5; 5; 3; 3; 1].

于是我写了一个暴力程序,第一组样例还真跑出一个 15 的答案来。

但是第二组 答案大小比样例少了1。

 

既然结果不正确,那就需要把那个正确的答案的路径输出来,看看有什么不同。

结果发现最终答案应该是上下两个的差不超过2.

于是我添加了一个 fix 函数,修正这种情况。

然后三个样例都过了。

再然后就是 WA 了。

 

正确的题意

然后我想还是想弄明白题意再说,于是用 [3,3; 2,2; 1,1] 模拟了一下,发现真的比 [3; 2; 1] 的答案的二倍少。

这时我意识到可能目标真的是求[1,1; 2,2; 3,3]  这种情况。

 

暴力DFS尝试

知道了题意,数据量只是到8,于是写了一个暴力程序。

使用 "1122334455" 串的形式map 了一下。

对于5瞬间跑出答案,对于6 跑了好一会。

 

双向DFS搜索

直接搜太慢,那就双向搜试试。

于是写了一个双向 DFS, 结果 6也是瞬间跑出来,但是 7 怎么也出不来了。

 

使用逆序数剪枝双向搜索

写的虽然是双向DFS,但是其实还是暴力搜索,还没有加什么剪枝。

于是使用 逆序数剪枝, 7 十秒多跑出来了。

于是提交试试,发现 超内存,现在不是时间问题了,是内存不够的问题了。

 

状态压缩

内存不够就要想法节省内存,其中 map<string, string>最浪费内存。

为什么要使用 string 呢?

为了保存一个状态。

那能不能使用位数压缩状态么?

发现还真的可以。

数字是从1-8,也就是0-7 了。最少需要三位才能表示一个数字,总共需要 24位数字,3字节,long long 类型的可以。

于是修改成map<LL, LL>.

为什么要使用 map 呢?

貌似是为了记录路径,这里不需要记录路径。

于是修改成为了 set<LL> .

再次提交还是超内存。

 

A* 算法出世

到底是为什么会超内存呢?

因为状态太多了。

为什么状态太多了呢?

因为我们使用的暴力搜索,我们不知道哪个状态是最优解,哪个不是。

那能不能确认某个状态一定比另一个状态更优呢?

貌似可以的。

那就用优先队列吧。

于是问问学弟小堆是使用大于号还是小于号。最后自己在模板生找到了。

 

A*搜索的估价函数

双向搜索时曾遇到过逆序数,于是使用逆序数作为估价函数吧。

7 终于跑出来了。

但是 8 还是跑步出来。

 

A*搜索的另一个估价函数

逆序数这个估价函数行吗?

貌似误差太大,无效状态太多。

那能不能换一个估价函数呢?

貌似还真有一个,每个数字离自己最终的位置的距离也是一个不错的估价汗是。

那就使用这个估价函数吧。

于是把估价函数换了换,结果还是只能跑出7来。

 

强强联合

怎么还是跑不出 8 呢?

估价函数太弱,精度太低。

那能不能加强估价函数呢?

貌似可以的。

比如说呢?

对于逆序数,交换一次最多减少3个逆序数,最少一个。

对于相对距离,交换一次最多减少两个,最少不变。

知道了,就这个办呢。

于是使用两个估计函数,重新了程序,结果7确实跑的快乐,但是还是跑不出8来。

 

总结

这道题虽然没有跑出 8 来,但是收获不少。

首先这一切都是自己独立思考的,再次开发了智力。

有兴趣的人可以继续思考下去,尽量不要看解题报告。

所有代码都在这里 https://github.com/tiankonguse/ACM/tree/master/hust/doublesort

 

参考

tiankonguse 的模板

0
0
分享到:
评论

相关推荐

    double_merge_sort.c

    double_merge_sort.c

    double类型精度丢失;double转换到64位整数

    double转换到64位整数”就涉及到这一关键概念。 精度丢失通常发生在以下几种情况: 1. **浮点数存储**: 浮点数在计算机内部是用二进制表示的,不是所有的小数都能精确地表示为有限的二进制小数,这就导致了精度...

    c++ string转换double

    这段代码定义了一个名为 `strDou` 的函数,该函数接收一个 `std::string` 类型的参数 `str`,并返回一个 `double` 类型的值。 **2. 字符数组分配** 首先,通过 `new` 操作符分配了一个长度为 `str.length()` 的...

    c++中double与string相互转换算法

    这行代码直接将`double`转换为对应的`std::string`。 接下来,我们来看`string`转`double`的方法。同样,`std::stringstream`在这里非常有用: ```cpp std::string str = "3.14"; std::stringstream ss(str); ...

    Java Double 精度问题总结

    ### Java Double 精度问题总结 在Java编程语言中,`double` 类型是一种用于表示64位浮点数的原始数据类型。虽然 `double` 提供了相对较高的精度,但在涉及精确数学运算(特别是涉及到小数值)时,由于其内部采用二...

    matlab开发-struct2double

    在提供的压缩包中,`struct2double.m`很可能是实现`struct2double`功能的MATLAB代码,而`license.txt`则包含了关于该函数的授权信息。通过阅读源代码,你可以更深入地了解其内部工作原理,这对于学习和定制函数非常...

    防止Double加double后形成科学计数法问题

    防止Double加double后形成科学计数法问题

    限制文本框只能输入double类型

    在C#中,我们可以使用事件处理器来监听文本框的键盘按键事件(`KeyPress`),通过检查用户输入的字符是否符合double类型的要求来实现这一功能。具体来说,我们需要关注以下几个关键点: 1. **字符有效性检查**:检查...

    C# Double保留小数点后面位数

    本文将围绕“C# Double保留小数点后面位数”这一主题展开详细讨论,包括如何利用`Double`类型的数据以及如何通过字符串格式化来实现这一功能。 ### C#中的Double类型 在C#中,`Double`是一种基本数据类型,用于...

    嵌入式系统开发人员C语言测试题-函数-选择题.doc

    (347) 这道题考察了函数的参数传递方式。由于c是函数的形参,故其值不会被保留到函数外部,因此输出结果为无法确定。 (348) 在C语言中,如果函数的返回值类型未指定,默认为int类型。 (349) 这道题考察了...

    java-16位内存数据转化为double型

    从给定的代码片段来看,这实际上是一段C++代码,而非Java代码,旨在将一个十六进制字符串转换为双精度浮点数(double)。在深入解析这段代码之前,我们首先来了解一下Java中如何实现16位内存数据转化为double型。 #...

    double数据类型

    根据IEEE 754标准,`double`类型的精度通常限制为大约15位有效数字,这在大多数情况下已经足够,但在涉及极端数值或高度敏感的计算时,例如财务计算等,这种精度可能不足以避免出现累积误差。 #### IEEE 754标准 ...

    TCP传输double数据.zip

    本项目“TCP传输double数据.zip”聚焦于利用TCP协议在客户端和服务器之间传输double类型的浮点数组,这对于分布式计算、数据同步以及其他需要大量数值交换的应用场景极具价值。以下将详细介绍TCP协议、数组传输过程...

    double to string

    在编程领域,将`double`类型的数值转换为`string`字符串是一个常见的操作,尤其是在处理数据输出、用户界面显示或者文件存储时。`double`是一种浮点数类型,它能表示较大的数值范围和精度,而`string`则常用于文本...

    double 计算过程出现的误差

    ### double计算过程中出现的误差分析 在计算机编程领域,尤其是涉及到数值运算时,经常会遇到由于浮点数表示不精确而导致的计算误差问题。本篇文章将深入探讨在C#、SQL Server以及Oracle数据库中使用`double`类型...

    BigDecimal向Double转换

    这是因为Double类型的精度是有限的,它只能存储大约15到16位的有效数字,而BigDecimal可以存储更多位数的数字。因此,在某些情况下,BigDecimal中的一些小数位可能会丢失。 #### 2.2.2 溢出问题 另外,如果...

    转换科学计数法成double

    输入一科学计数法形式字符串,如1234.5e-6 ;通过double atof()将其转换成double形的数据

    float、double类型介绍.zip

    描述中的链接指向了一个CSDN博客文章,作者分享了关于float和double类型的详细讲解。在这个博客中,作者可能讨论了以下内容: 1. **浮点数表示法**:讲解了浮点数如何用二进制表示,包括指数和尾数的概念。 2. **...

    Java Double相加出现的怪事

    Java 中的浮点数类型 float 和 double 在进行运算时会出现不精确的问题,这是因为计算机无法精确地表示十进制小数。这种问题不仅存在于 Java 中,在其它许多编程语言中也存在。 问题的提出: 编译运行下面的 Java ...

    2.double dqn.ipynb

    关于double dqn的例子,适合初学者对深度强化学习double dqn的认识和了解

Global site tag (gtag.js) - Google Analytics