Codeforces 873D. Merge Sort 分治 + 构造 - WA是一笔财富 - CSDN博客



Codeforces 873D. Merge Sort 分治 + 构造 - WA是一笔财富 - CSDN博客

题意：给出一种特殊的归并排序，分治的方法同普通的归并排序一样，只是如果当前待排序的区间已经是有序的，就不会再继续递归了，让你构造一个会调用k次mergesort函数的序列。

思路：因为我们上来就会调用一次mergesort函数，并且只要当前待排序区间不是有序的，那么在该层递归里就会调用两次mergesort，因此可以推出总调用次数一定是个奇数。然后我们递归的构造答案序列（令答案序列初始有序），若k > 2, 我们就将当前区间的a[mid]和a[mid - 1]交换一下，这样可以保证下一层递归传进去的区间一定是个有序区间，这不会样影响k==1时候的退出（按照题给定义，必须当前区间有序才能退出）。交换后k就少了2，一直这样递归构造，出口就是l + 1 == r或者k == 1.


Read full article from Codeforces 873D. Merge Sort 分治 + 构造 - WA是一笔财富 - CSDN博客


No comments:

Post a Comment

Subscribe to: Post Comments (Atom)

Labels

Algorithm (219) Lucene (130) LeetCode (97) Database (36) Data Structure (33) text mining (28) Solr (27) java (27) Mathematical Algorithm (26) Difficult Algorithm (25) Logic Thinking (23) Puzzles (23) Bit Algorithms (22) Math (21) List (20) Dynamic Programming (19) Linux (19) Tree (18) Machine Learning (15) EPI (11) Queue (11) Smart Algorithm (11) Operating System (9) Java Basic (8) Recursive Algorithm (8) Stack (8) Eclipse (7) Scala (7) Tika (7) J2EE (6) Monitoring (6) Trie (6) Concurrency (5) Geometry Algorithm (5) Greedy Algorithm (5) Mahout (5) MySQL (5) xpost (5) C (4) Interview (4) Vi (4) regular expression (4) to-do (4) C++ (3) Chrome (3) Divide and Conquer (3) Graph Algorithm (3) Permutation (3) Powershell (3) Random (3) Segment Tree (3) UIMA (3) Union-Find (3) Video (3) Virtualization (3) Windows (3) XML (3) Advanced Data Structure (2) Android (2) Bash (2) Classic Algorithm (2) Debugging (2) Design Pattern (2) Google (2) Hadoop (2) Java Collections (2) Markov Chains (2) Probabilities (2) Shell (2) Site (2) Web Development (2) Workplace (2) angularjs (2) .Net (1) Amazon Interview (1) Android Studio (1) Array (1) Boilerpipe (1) Book Notes (1) ChromeOS (1) Chromebook (1) Codility (1) Desgin (1) Design (1) Divide and Conqure (1) GAE (1) Google Interview (1) Great Stuff (1) Hash (1) High Tech Companies (1) Improving (1) LifeTips (1) Maven (1) Network (1) Performance (1) Programming (1) Resources (1) Sampling (1) Sed (1) Smart Thinking (1) Sort (1) Spark (1) Stanford NLP (1) System Design (1) Trove (1) VIP (1) tools (1)

Popular Posts