Memory of Cutey

简介：归并排序(merging sort)的时间复杂度为O(nlogn)，是一种稳定的排序方法。常用的2-路归并排序中的核心操作是将一维数组中前后相邻的两个有序序列归并为一个有序序列，递归算法形式简洁，简单易用。

应用1：求逆序对数

设a[1...n]是一个包含n个不同数的数组，对于i<j如有a[i]>a[j]，则称(i,j)为一个逆序对。出题方式很多，比如直接求一个序列中逆序对的个数；比如交换原序列中相邻两元素位置使之成为单调不下降序列，求交换次数等等。当然，求逆序对数的方法也很多，但时间复杂度不大于O(nlogn)就只有归并排序和平衡二叉树了吧，显然归并排序实现起来更加简单，代码如下所示。

#include <stdio.h>

#define MAX 50001
int temp[MAX];
int count, n;

void Merge(int *array, int s, int m, int t)
{
	int i=s, j, k;
	for (j=m+1,k=s; s<=m&&j<=t; ++k)
	{
		if (array[s]<=array[j])
			temp[k] = array[s++];
		else
		{
			temp[k] = array[j++];
			count += m-s+1;  //record the inversion pairs
		}
	}
	while (s<=m)
		temp[k++] = array[s++];
	while (j<=t)
		temp[k++] = array[j++];
	while (i<=t)
		array[i] = temp[i++];
}

void MergeSort(int *array, int s, int t)
{
	if (s!=t)
	{
		int m;
		m = (s+t)/2;
		MergeSort(array,s,m);
		MergeSort(array,m+1,t);
		Merge(array,s,m,t);
	}
}

int main()
{
	int i;
	while (1)
	{
		count = 0;
		printf("Input the number(1~50000):");
		scanf("%d", &n);
		if (n==0)
			break;
		int array[n+1];
		for (i=1; i<=n; i++)
			scanf("%d", &array[i]);
		printf("The initial sequence is: ");
		for (i=1; i<=n; i++)
			printf("%d  ", array[i]);
		printf("\n");
		MergeSort(array, 1, n);
		printf("The sorted sequence is:  ");
		for (i=1; i<=n; i++)
			printf("%d  ", array[i]);
		printf("\nThe count of inversions is: %d\n", count);
	}
	return 0;
}

p.s.上述代码如果编译有错误的只需将第50行的int array[n+1];换成int array[MAX];就可以了，支持不定长数组是C99标准新增的特性，我平时使用的GCC是完全支持C99标准的，所以编译没问题，但是VS就不行了，呵呵。

应用2：其实也是求逆序对，只不过比较隐晦的那种

（阅读全文……）

致广大QQ用户的一封信

亲爱的QQ用户：

当您看到这封信的时候，我们刚刚作出了一个非常艰难的决定。在360公司停止对QQ进行外挂侵犯和恶意诋毁之前，我们决定将在装有360软件的电脑上停止运行QQ软件。我们深知这样会给您造成一定的不便，我们诚恳地向您致歉。同时也把作出这一决定的原因写在下面，盼望得到您的理解和支持。

一、保障您的QQ帐户安全

近期360强制推广并胁迫用户安装非法外挂“扣扣保镖”。该软件劫持了QQ的安全模块，导致了QQ失去相关功能。在360软件运行环境下，我们无法保障您的QQ帐户安全。

二、对没有道德底线的行为说不

360屡屡制造“QQ侵犯用户隐私”的谣言，对QQ的安全功能进行恶意污蔑。事实上QQ安全模块绝没有进行任何用户隐私数据的扫描、监控，更绝对没有上传用户数据。目前我们已经将QQ安全模块代码交由第三方机构检测，以证明我们的清白。

更甚的是，360作为一家互联网安全公司，竟推出外挂软件，公然站到了“安全”的对立面，对其他公司的软件进行劫持和控制。这些都是没有道德底线的行为。

（阅读全文……）

前几天终于耐不住寂寞，把台式机的XP换成了Win 7，也顺便将Ubuntu升级到了10.10。重装系统什么的最讨厌了，还要装各种软件，装软件也就罢了，还要进行各种升级，各种安装，各种配置，真是各种麻烦。

由于某次直接从9.04在线升级到9.10时出现了可怕的问题，搞了好久才恢复好，所以现在Ubuntu版本升级都是采取重装的方式。装好了首先要进行update，不知道是实验室网速的问题还是10.10源太少的问题，总之那个速度和乌龟爬没有太大区别。

由于10.10现在好像还没有太好用的源，所以直接采取寻最优源的方法。我发现好多人是不知道怎么寻最优源的，其实很简单，只需以下几步。

1) 找到System->Administration->Update Manager，然后点击Settings打开Software Sources，选择Ubuntu Software选项。

2)  在Download from框中选择Other，进入下图所示对话框，然后点击Select Best Server，等待系统帮忙选好了之后再点Choose Server确认就好了。

（阅读全文……）

天空下着雨，却挡不住我们相爱的脚步。

牵着你的手在雨中行走，假装欣赏着雨中的风景。

天真的我希望这雨永远下着不要停，以为只要雨不停我们就可以这样一直走下去。

爱你的我只希望紧紧的靠着你，感受只属于我的，你的气息。

昔日的足球场因为下雨空无一人，现在的它成了我们的天地。

我张开双臂，大声的告诉天空，这大片的广阔都是属于我，你也属于我。

（阅读全文……）

我觉得我最近真的是懒死了，虽然一直以自己很忙为借口，但是确实是自己没有把时间利用好，而且，最近早晨居然起不来床了，噩梦啊。

今天本来是准备写篇纪念文的，结果中午被豆豆训了，想想他对我也没那么好，就不专门写了，只拿出一篇以前的回味下初恋时的味道吧，嘿嘿。

刚才，负责我现在项目的老师又来说了下小论文和开题的事情，转眼间还有一个月就要开题了，小论文也要开始写了，瞬间又感到了众多压力，虽然老师一直说这些都很简单啦，但我还是有那么一点点紧张的。因为项目年底就要结题，所以东西和论文都要在结题前出来，其实这样对我是挺好的，下学期就没什么压力了，不过这学期就要辛苦好多。

不过还好目标比较明确，这学期只要好好把项目做完，然后发一篇小论文就圆满了。嗯，好好努力，争取早完工早回家，呃，想家了。

由于项目需要，最近一直在linux操作系统，由于个人需要，最近一直在使用webqq。由于qq for linux不好用，时常自动关闭，用户体验也做的不好，反而是webqq更加常用。

webqq2.0华丽上线，确实给人小小的震撼，很多评论都在说“TX要出操作系统了吗”，这个架势确实有点操作系统的感觉了。浏览网页、腾讯微博、QQ地图、糗事百科、股票、天气、搜索，各种应用，几乎可以满足所有需求；右下方设有按钮点击直接打开QQ云输入法，正好解决了linux自带输入法在网页中不时出现异常的问题；更值得一提的是可以从应用中直接打开Gmail，无疑讨好了Gmail的广大粉丝。

能够用到如此友好而强大的webqq是linux用户的幸福，腾讯在这一点确实做的不错，虽然仍存在些问题，但是现在是测试版嘛，相信正式版应该会更加完美的。

1. 以前的webqq每当收到新的消息时，网页的标题会出现提示，那么即使你当时在浏览其他的网页也会即时发现有新消息，但是webqq2.0没有提示，不知道是测试版的缘故，还是webqq真的想做成“网页操作系统”，我只想说大多数人还是仅仅把webqq打开就去干别的了，不可能一直盯着那个页面，所以标题栏的提示还是应该有的。

2. 今天登webqq2.0可能是长时间未操作的缘故，居然自动下线了，其实下线也就罢了，关键是没有任何提示，而且状态也还是显示在线，只是发送消息发不出去，无语，只要退出了重新登一遍。

今天用了一上午，目前就发现这两个问题，总体还是非常不错的，TX果然V5，呵呵。

最后，给个门支持一下：web2.qq.com

C语言可以说是我学习的第一门语言，不过似乎也是忘的最多的一门语言，自从因为项目需要重新拾起C语言，我的噩梦就开始了。

依稀记得大二学习数据结构时编程解决“约瑟夫环”、“迷宫”等问题后的骄傲，认为C简直就是天神一般的语言，如此强大，如此让人着迷。后来学了C++，后来开始搞.net，后来自学了CSS和简要的PHP，当C快被我抛弃的时候，由于种种原因，被分到一个新的项目，重新开始做C编程。

继语法树构造完之后自我放假了好久，这两天开工写了一段文件处理的代码，发现以前学习的C语言知识确实完全还给老师了，小崔，我对不起你啊，下面是遭遇问题小结。

1. 字符型转化为整型

如果不是正好用到，我想我永远不会知道居然还有标准库函数可以将字符串转换为任意类型（整型、长整型、浮点型等），我太无知了，我居然只知道强制类型转换，却从来没想过对于字符串要怎样处理，不过还好有人跟我一样不知道，哼哼。

atof()：将字符串转换为双精度浮点型值；
atoi()：将字符串转换为整型值；
atol()：将字符串转换为长整型值；
strtod()：将字符串转换为双精度浮点型值，并报告不能被转换的所有剩余数字；
strtol()：将字符串转换为长整值，并报告不能被转换的所有剩余数字；
strtoul()：将字符串转换为无符号长整型值，并报告不能被转换的所有剩余数字。

用法非常简单，举例说明如下：
（阅读全文……）

S04E01 集名：The Robotic Manipulation

播出时间：9月23日（北京时间9月24日）

TBBT新季驾到，大家尽情发挥想象吧，制片Bill Prady一再强调，新季的剧情绝对让人意想不到。

（阅读全文……）

有人问佛祖：“天上会掉馅饼吗？”
佛祖说：“会，但是你有本事接住它吗？”

前几天手机信号不是很好，豆豆问“你的手机信号最近怎么总是这么烂？”，我说“因为她想要下岗了，因为她听到iPhone 4在召唤我…”，豆豆很绝望，他知道我又在胡言乱语了，正处于经济危机的我是绝对没有钱去买iPhone 4的，虽然我现在已经被她迷晕了，但是资金有限，只能眼馋喽。

华丽丽的iPhone 4，外表完美的几乎无懈可击，9.3毫米的厚度，960×640的分辨率，以及还停留在想象层面的温润如玉的触觉，OMG，真的是让人看一眼就想拥有啊。

好吧，等咱有了钱，一下买两台，小白自己用，小黑给豆豆，不过现在，就先观望吧。