h873. 排序問題
標籤 : sort 線段樹
通過比率 : 7人/13人 ( 54% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-04-15 10:42

內容

排序有很多種,像是經典的bubble sort,或是快的merge sort,有的時候會被卡的quick sort,甚至是很神奇的bogo sort,以及很難實現的gravity sort……,總之排序是個有趣的東西,所以現在給你個A陣列以及B陣列,他們長度為N,想要問你一題和排序有關的問題

你現在可以對A陣列進行任意次的sort操作,你每次的操作可以選擇一個連續區間[L,R],把此區間裡的數依照大小地從小到大排序,小的放前面大的放後面

你的目標是判斷A陣列有沒有機會在透過一系列的操作後變得跟B陣列一樣。

範圍限制:

1 ≤ N ≤ 105
1 ≤
Ai, Bi ≤ N

輸入說明

首先第一行有一個數N,代表AB陣列的長度。
再來兩行各N個數代表陣列內容。

輸出說明

輸出答案yesno,代表可不可能透過一系列sort操作來把A陣列轉成B

範例輸入 #1
7
3 2 1 4 3 1 1 
3 1 2 4 1 1 3
範例輸出 #1
yes
範例輸入 #2
4
1 2 4 3
3 4 1 2
範例輸出 #2
no
範例輸入 #3
3
1 2 3
2 3 4
範例輸出 #3
no
測資資訊:
記憶體限制: 256 MB
不公開 測資點#0 (10%): 1.0s , <1K
不公開 測資點#1 (10%): 1.0s , <1K
不公開 測資點#2 (10%): 1.0s , <1K
不公開 測資點#3 (10%): 1.0s , <10M
不公開 測資點#4 (10%): 1.0s , <1M
不公開 測資點#5 (10%): 1.0s , <1M
不公開 測資點#6 (10%): 1.0s , <1M
不公開 測資點#7 (10%): 1.0s , <10M
不公開 測資點#8 (10%): 1.0s , <10M
不公開 測資點#9 (10%): 1.0s , <10M
提示 :

範例參考:

#1 您可以先sort區間[2,3]接著sort區間[5,7]

#2 沒有任何方法可以把A變成B

#3 請注意A陣列和B陣列內容可能不一樣

標籤:
sort 線段樹
出處:
Chi's Coding Problem [管理者: Ststone1687 (Ststone) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」