某工廠收到了 n 個(gè)產(chǎn)品的訂單,這 n 個(gè)產(chǎn)品分別在 A、B 兩個(gè)車間加工,并且必須先在 A 車間加工后才可以到 B 車間加工。
某個(gè)產(chǎn)品 i 在 A,B 兩車間加工的時(shí)間分別為Ai,Bi。怎樣安排這 n 個(gè)產(chǎn)品的加工順序,才能使總的加工時(shí)間最短。
這里所說的加工時(shí)間是指:從開始加工第一個(gè)產(chǎn)品到最后所有的產(chǎn)品都已在 A,B 兩車間加工完畢的時(shí)間。
第一行僅—個(gè)數(shù)據(jù) n ,表示產(chǎn)品的數(shù)量;
接下來 n 個(gè)數(shù)據(jù)是表示這 n 個(gè)產(chǎn)品在 A 車間加工各自所要的時(shí)間;
最后的 n 個(gè)數(shù)據(jù)是表示這 n 個(gè)產(chǎn)品在 B 車間加工各自所要的時(shí)間。
第一行一個(gè)數(shù)據(jù),表示最少的加工時(shí)間;
第二行是一種最小加工時(shí)間的加工順序。
5 3 5 8 7 10 6 2 1 4 9
34 1 5 4 2 3
對(duì)于100%的數(shù)據(jù), 0 < n < 10000,所有數(shù)值皆為整數(shù)。