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. */

複製代碼

may

1. //#include <iostream>
   
2. //#include <vector>
   
3. //#include <algorithm>
   
4. #include <bits/stdc++.h>
   
5. using namespace std;
   
6. 
   
7. // 定義檔案結構體
   
8. struct File {
   
9.     int name;//檔案名稱
   
10.     int modified_time;//修改時間
    
11.     int type;//檔案類型
    
12.     int size;//檔案大小
    
13.     int original_index; // 紀錄初始索引，確保穩定排序
    
14. };
    
15. 
    
16. // 比較函數類別，用來根據指定屬性進行排序
    
17. class FileComparator {
    
18. private:
    
19.     int attribute;//屬性
    
20.     bool ascending;//排序順序
    
21. 
    
22. public:
    
23.     FileComparator(int attr, bool asc) : attribute(attr), ascending(asc) {}//定義排序邏輯，根據傳入的屬性 (attribute) 和排序順序 (ascending) 進行比較
    
24. 
    
25.     bool operator()(const File a, const File b) {
    
26.         int valA, valB;
    
27. 
    
28.         // 根據屬性選擇比較值
    
29.         switch (attribute) {
    
30.             case 1: valA = a.name; valB = b.name; break;
    
31.             case 2: valA = a.modified_time; valB = b.modified_time; break;
    
32.             case 3: valA = a.type; valB = b.type; break;
    
33.             case 4: valA = a.size; valB = b.size; break;
    
34.             default: return false;
    
35.         }
    
36. 
    
37.         // 進行升序或降序比較
    
38.         if (valA != valB)
    
39.             return ascending ? (valA < valB) : (valA > valB);
    
40. 
    
41.         // 如果屬性值相同，按原始順序排序
    
42.         return a.original_index < b.original_index;
    
43.     }
    
44. };
    
45. 
    
46. int main() {
    
47.     int N, K;
    
48.     cin >> N >> K;
    
49. 
    
50.     vector<File> files(N);
    
51. 
    
52.     // 讀入檔案資料
    
53.     for (int i = 0; i < N; i++) {
    
54.         cin >> files[i].name >> files[i].modified_time >> files[i].type >> files[i].size;
    
55.         files[i].original_index = i;
    
56.     }
    
57. 
    
58.     vector<int> operations(K);
    
59. 
    
60.     // 讀入操作資料
    
61.     for (int i = 0; i < K; i++) {
    
62.         cin >> operations[i];
    
63.     }
    
64. 
    
65.     // 記錄每個屬性目前的升降序狀態，預設為升序
    
66.     vector<bool> ascending(5, true);
    
67. 
    
68.     // 按操作順序進行排序
    
69.     for (int op : operations) {
    
70.         // 依指定屬性排序
    
71.         sort(files.begin(), files.end(), FileComparator(op, ascending[op]));
    
72. 
    
73.         // 切換該屬性的升降序狀態
    
74.         ascending[op] = !ascending[op];
    
75.     }
    
76. 
    
77.     // 輸出結果
    
78.     for (const auto file : files) {
    
79.         cout << file.name << " " << file.modified_time << " " << file.type << " " << file.size << endl;
    
80.     }
    
81. 
    
82.     return 0;
    
83. }
    
84. /*
    
85. 3 7
    
86. 1 2 5 8
    
87. 2 4 6 8
    
88. 3 3 6 7
    
89. 2 2 2 3 3 3 3
    
90. */

複製代碼

-----------------------------------------------------------------
程式解說
結構體定義：

定義了一個 File 結構體，包含四個屬性（檔案名稱、修改時間、檔案類型、檔案大小）和初始索引 original_index，用來保持穩定排序。
比較器：

使用 FileComparator 類別定義排序邏輯，根據傳入的屬性 (attribute) 和排序順序 (ascending) 進行比較。
如果兩個檔案的指定屬性值相同，會依照初始順序比較（original_index）。
排序操作：

使用 std::sort 函數按照指定屬性進行排序，並在排序完成後切換該屬性的升降序狀態。
主要邏輯：

按輸入順序執行所有的排序操作。
每次操作後更新對應屬性的排序順序。
輸入與輸出：

程式會依照範例輸入進行排序，最後輸出最終排序後的檔案屬性資料。
範例輸入與輸出
輸入：

複製程式碼
5 3
5 10 1 50
1 20 3 30
3 15 2 40
2 25 1 20
4 5 2 10
1 3 3
輸出：

複製程式碼
2 25 1 20
5 10 1 50
3 15 2 40
4 5 2 10
1 20 3 30
重點特性
使用穩定排序來維持原始順序的穩定性。
動態切換升降序狀態，模擬使用者連續點擊的操作。
高效處理多屬性排序問題，適用於實際應用場景。