202409潛力1-檔案順序files

may

檔案順序 (Files)
問題敘述  
在圖形化介面的作業系統中，檔案列出的順序可以由使用者的需求自訂，只要一次點擊就能夠即時地根據某個屬性的數值重新排列不同檔案。常用可排序的屬性包含：檔案名稱、修改時間、檔案類型、檔案大小等，每種屬性支援從小到大或從大到小的排序。  
請實作一支程式模擬系統排序若干個檔案數次後的結果。為了方便起見，關於檔案的所有資料都會以正整數的方式呈現，排序時也使用整數的比較方式（而非當成字串使用字典順序比較），也就是在遞增排序時 117 會排在 12 的後面。   
假設系統中現在一共有五個檔案，一開始的順序如下表所示：  


   當使用者第一次點選某個屬性時，會將所有檔案以該屬性升序排列。假設使用者點選了「檔案名稱」時，這些檔案的順序會變成：  



接著使用者點選「檔案類型」時，這些檔案就會被用檔案類型升序排列；在依據某條件排序的過程中，若有相同數值則會依照操作之前的順序排列（第一個操作則是根據測資輸入的順序），因此會變成：



當使用者連續點選了某個屬性多次時，會切換該屬性排列的升降序，也就是將升序排列變成降序排列，或者反過來。注意這個改變並不是將順序以完全相反方式呈現，因此其他屬性仍然會保持之前的順序。假設使用者在上一個操作後再次點選了「檔案類型」，也就是連續點選了檔案類型兩次，則這些檔案會被以檔案類型進行降序排列，變成：


輸入格式
第一列有兩個正整數N 與 ，代表檔案的數量以及使用者點選操作的次數。
接下來有 N 列，每一列有四個整數，依序代表該檔案的四個屬性：檔案名稱、修改時間、檔案類型和檔案大小。所有數值介於0到109之間，且保證檔案名稱跟修改時間不會重複。
最後一列有K個整數，代表使用者依序點選了哪一個屬性。屬性只有可能是1代表檔案名稱、2代表修改時間、3代表檔案類型、4代表檔案大小四種。

輸出格式
請輸出N列，每一列4個整數，代表最後一個操作結束後排序完畢的檔案資料。同一列的兩個整數間以一個空白隔開。


輸入範例的說明：
範例 1即是問題敘述內的情形。
在範例2中，一開始點擊三次修改時間後會以修改時間升序排列，檔案名稱的順序會變成 1, 3, 2，接著再點擊四次檔案類型後會以檔案類型降序排列。

評分說明 此題目測資分成五組，每組測資有多筆測試資料，需答對該組所有測試資料才能獲得該組分數，各組詳細限制如下。
第一組（20分）：N ≤ 500、K = 1，且檔案類型和檔案大小的數值皆不重複。
第二組（20分）：N ≤ 500，且不會連續點擊兩次相同屬性。
第三組（20分）：K = 1，且檔案類型和檔案大小的數值皆不重複。
第四組（20分）：不會連續點擊兩次相同屬性。
第五組（20分）：無特別限制。

https://zerojudge.tw/ShowProblem?problemid=o626

may

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. struct File{
   
5.     int fileInfo[5] = {0};
   
6. };
   
7. 
   
8. class Cmp{
   
9. public:
   
10.     bool operator() (const File &lhs, const File &rhs)
    
11.     {
    
12.         for(auto i: Cmp::sort_order)
    
13.         {
    
14.             if(i<0)
    
15.             {
    
16.                 i *= -1;
    
17.                 if(lhs.fileInfo[i]!=rhs.fileInfo[i])
    
18.                     return lhs.fileInfo[i]>rhs.fileInfo[i];
    
19.             }
    
20.             else
    
21.             {
    
22.                 if(lhs.fileInfo[i]!=rhs.fileInfo[i])
    
23.                     return lhs.fileInfo[i]<rhs.fileInfo[i];
    
24.             }
    
25.         }
    
26.         return false;
    
27.     }
    
28.     static vector<int> sort_order;
    
29. };
    
30. 
    
31. vector<int> Cmp::sort_order;
    
32. int main()
    
33. {
    
34.     Cmp::sort_order.clear();
    
35.     int N, K;
    
36.     cin >> N >> K;
    
37.     vector<File> lists(N);
    
38.     for(int i=0; i<N; ++i)
    
39.     {
    
40.         File &f = lists[i];
    
41.         for(int info=0; info<4; ++info)
    
42.             cin >> f.fileInfo[info+1];
    
43.         f.fileInfo[0] = i;
    
44.     }
    
45. 
    
46.     vector<int> orders(K);
    
47.     for(auto &i:orders)
    
48.         cin >> i;
    
49.     reverse(orders.begin(), orders.end());
    
50. 
    
51.     //process click orders
    
52.     vector<bool> appeared(5, false);
    
53.     int prev = orders[0], cnt = 1;
    
54.     for(int i=1; i<orders.size(); ++i)
    
55.     {
    
56.         if(orders[i]==prev)cnt += 1;
    
57.         else
    
58.         {
    
59.             if(appeared[prev]==false)
    
60.             {
    
61.                 appeared[prev] = true;
    
62.                 if(cnt%2==0)prev *= -1;
    
63.                 Cmp::sort_order.push_back(prev);
    
64.             }
    
65.             cnt = 1;
    
66.         }
    
67.         prev = orders[i];
    
68.     }
    
69.     if(appeared[prev]==false)
    
70.     {
    
71.         if(cnt%2==0)prev *= -1;
    
72.         Cmp::sort_order.push_back(prev);
    
73.     }
    
74.     Cmp::sort_order.push_back(0);
    
75. 
    
76.     sort(lists.begin(), lists.end(), Cmp());
    
77.     for(auto &f: lists)
    
78.     {
    
79.         for(int i=1; i<=4; ++i)
    
80.         {
    
81.             cout << f.fileInfo[i] << ' ';
    
82.         }
    
83.         cout << '\n';
    
84.     }
    
85.     return 0;
    
86. }
    
87. /*
    
88. 3 7
    
89. 1 2 5 8
    
90. 2 4 6 8
    
91. 3 3 6 7
    
92. 2 2 2 3 3 3 3
    
93. */

複製代碼