作者gene07 (-.-)
看板java
标题Re: [问题] 资料的比较、插入、排序
时间Tue Sep 6 15:43:24 2016
※ 引述《cowbaying (是在靠北喔)》之铭言：
: schedule.addtask(new Task(2, 20, 'A1'));
: schedule.addtask(new Task(8, 10, 'A2'));
: schedule.addtask(new Task(10, 15, 'A3'));
: schedule.addtask(new Task(12, 10, 'A4'));
: taskBs.add(new Task(2, 2, 'B1')); (实际长度8)
: taskBs.add(new Task(12, 10, 'B2')); (实际长度26)
: taskBs.add(new Task(22, 3, 'B3')); (实际长度29)
: taskBs.add(new Task(12, 50, 'B4')); (实际长度66)
: A1 A2 A3 A4
: |>!---------|>>>>-----|>>>>>-------|>>>>>>-----
: |>-! |>>>>>>-----|>>>>>>>>>>>-|>>~~~
: B1 B2 B3 B4
: 我对这个机制的理解如上图
: A是主要的
: B能否执行要看A延迟的时间是否足够把B插入、执行、延迟跟切换回A的时间容纳进去
: 原PO的文字描述实在是看不太懂
: 如果B的延迟时间会连带延迟到A的时间
: 那麽根本不须排序了
: A执行完换B就好
我的意思是...
假设...
(4,10,'A1') | (2,2,'B1')
|
(4,10,'A2') | (2,20,'B2')
|
(2,5,'A3') | (2,5,'B3')
A1 A2
|>!--------------------------------------|>!-------
(往B,2秒)|>!------------------|>!---------------
B1 (B1做完delay 2s) B2 (B往A,2秒)
这样刚好从A到B来回一次4秒+B1执行的两秒和delay两秒+B2的执行2秒
刚好可以插入到A1的delay10秒内...而B2的delay 20秒是从B回到A开始算
所以A2开始执行时B2 delay剩18秒..A2动作做完B2 delay剩14秒
A2 delay 10秒结束B2 delay剩10秒 A3动作做完B2 delay剩2秒
此时A移动到B刚好2秒 可以执行B3
应此就可以成功排序成 A1 B1 B2 A2 A3 B3
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 60.250.82.82
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/java/M.1473147809.A.FFB.html
1F：推 cowbaying: 我大概了解了 B的延迟可以切割 09/08 13:38
我完全没有头绪...~"~
2F：→ cowbaying: 你等我用FX写一个有进度表的模拟程式给你看看吧 XD 09/08 18:51
鲁弟我想到了一个方法，不知道这样行不行....
(4,10,'A1') | (2,2,'B1')
|
(4,10,'A2') | (2,20,'B2')
|
(2,5,'A3') | (2,5,'B3')
创一个最後输出的array
然後把执行动作和delay的时间都拆成1秒1秒去判断
执行动作假设为1，delay动作为0
A1 (往B移两秒) A2 (往B移两秒) A3
1,1,1,1,1,1,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,0,1,1,1,1,0,0,0,0,0
(往A移动两秒) (往A移动两秒)
B1 B2 B3
1,1,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0
然後把A动作跟B动作去做 & 如果不行A就往後一格继续跟B比较，
全部都等於0代表排序完成
※ 编辑: gene07 (36.230.202.56), 09/09/2016 22:25:29
3F：→ ssccg: 一秒一秒去比是对的，但是不用把输出转出来，用范围去比 09/10 09:37
4F：→ ssccg: 但是就是我之前说的，如果输入n个，每个值为k bit，这演算 09/10 09:43
5F：→ ssccg: 法复杂度是O(n^2 * 2^k)，虽然是对的... 09/10 09:44
6F：→ ssccg: 其实我一开始想到的作法就是 09/10 09:45
7F：→ ssccg: AAAAAA********AAAAAA********AAAA***(後面可补*****... 09/10 09:47
8F：→ ssccg: BBBBBBBB******************BBBB*** 09/10 09:48
9F：→ ssccg: 然後直接用string match的演算法去跑就好了 09/10 09:50