分治法的经典运用归并排序(Merge Sort)

简介归并排序(英语:Merge sort,或mergesort),是创建在归并操作上的一种有效的排序算法,效率为O(n log n)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。分类排序算法数据结构数组最差时间复杂度最优时间复杂度平均时间复杂度最差空间复杂度归并操作归并操作(merge),也叫归并算法,指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。迭代法申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列设定两个指针,最初位置分别为两个已经排序序列的起始位置比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置重复步骤3直到某一指针到达序列尾将另一序列剩下的所有元素直接复制到合并序列尾递归法原理如下(假设序列共有n个元素)... Read More

拆分集合为两个和相等的子集合问题(动态规划)

题意问题描述:将1到N的连续整数组成的集合划分为两个子集合,且保证每个集合的数字和相等。例如,对于N=4,对应的集合{1,2,3,4},能被划分为{1,4}、{2,3}两个集合,使得1+4=2+3,且划分方案只有此一种。编程实现给定任一正整数N(1<=N<=39),输出其符合题意的划分方案数。样例输入1:样例输出1:1    (可划分为{1,2}、{3}样例输入2:样例输出2:1    (可划分为{1,3}、{2,4}样例输入3:样例输出3:4    (可划分为{1,6,7}、{2,3,4,5},或{1,2,4,7}、{3,5,6},或{1,3,4,6}、{2,5,7},或{1,2,5,6}、{3,4,7}思路根据动态规划思想,可以得到状态转移方程如下[code lang="php"$d[$i][$j] = $d[$i - 1][$j] + $d[$i - 1][$j - $... Read More

Codeforces Round #345 (Div. 1) B Image Preview

原题B. Image Previetime limit per test1 seconmemory limit per test256 megabyteinputstandard inpuoutputstandard outpuVasya's telephone contains n photos. Photo number 1 is currently opened on the phone. It is allowed to move left and right to the adjacent photo by swiping finger over the screen. If you swipe left from the first photo, you reach photo n. Similarly, by swiping right from the last ... Read More

Codeforces Round #345 (Div. 1) A watchmen

原题A. Watchmetime limit per tes3 secondmemory limit per tes256 megabyteinpustandard inpuoutpustandard outpuWatchmen are in a danger and Doctor Manhattan together with his friend Daniel Dreiberg should warn them as soon as possible. There are n watchmen on a plane, the i-th watchman is located at point (xi, yi).They need to arrange a plan, but there are some difficulties on their way. As yo... Read More