[其他] 特殊排序(breadsorting)的理解與一般化

看板Math作者expiate (彎曲屎殼郎)時間5年前 (2020/09/23 09:08)推噓2(2推 0噓 27→)

留言29則, 2人參與討論串1/3 (看更多)

這是題目的網址：https://open.kattis.com/problems/bread 這題目的重點如下： - 三個相鄰的數字可以做旋轉，例如3,5,4 -> 4,3,5 -> 5,4,3 - 大小為n的array裡面有n個相異的整數，其值為1,2,3,...,n - 給你一個起始的數列與最終的數列，回答可否藉由旋轉來完成轉換 EX1: n: 4 起始：1 3 4 2 最終：4 3 2 1 1 3 4 2 ->4 1 3 2 ->4 2 1 3 ->4 3 2 1 (Possible) 我在網路上搜尋到的解法是，對於 1 2 3 4這個數列，起始與最終轉換到1 2 3 4 是否滿足某個性質：對起始與最終數列，分別加總小於目前數值的個數，其相差如果是偶數則是 possible (如解釋不清楚，可以參照我下面的程式碼) 我對這演算法正確性的理解是 - 相異的數，所以兩個數的關係不是小於就是大於 - 計算小於的個數等同於計算大於的個數 - 旋轉的關係會導致小於個數的變化 - 當3個相鄰的數時，我們只要確定相差是2的倍數即可保證可轉換 - 一般化來講，當k個相鄰的數時，是否要相差k-1的倍數才可保證能轉換? + 我是計算關係個數改變來做以上推斷我比較沒有信心的部分是這種存在性，看似好像合理但我又不是很確定是否真的有一系列的步驟可以完成這樣的轉換。也就是存在反例來打我臉XD 這邊不知道有沒有人可以理解我的擔憂? 我覺得好像還差一個步驟來完成這個一般化證明先謝謝了 code: int count(vector<int> &arr, int idx, int n){ int cnt=0; for(int i=idx+1;i<n;++i) if(arr[i]<arr[idx]) ++cnt; return cnt; } int main(){ int n; cin >> n; vector<int> org(n); vector<int> target(n); for(int i=0;i<n;++i) cin >> org[i]; for(int i=0;i<n;++i) cin >> target[i]; int res1=0,res2=0; for(int i=0;i<n;++i){ res1 += count(org,i,n); res2 += count(target,i,n); } if(abs(res1-res2)%2==0) cout << "Possible" << endl; else cout << "Impossible" << endl; return 0; } -- 天下英雄出我輩，一入江湖歲月催。鴻圖霸業談笑間，不勝人生一場醉。提劍跨騎揮鬼雨，白骨如山鳥驚飛。塵世如潮人如水，只嘆江湖幾人回。 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 98.207.101.195 (美國) ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1600823286.A.845.html

推