Board logo

標題: 202409潛力1-檔案順序files [打印本頁]
作者: may    時間: 2024-10-20 15:07     標題: 202409潛力1-檔案順序files

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

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


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


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

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

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

輸入範例的說明：
範例 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    時間: 2024-10-20 21:22

  1. #include <bits/stdc++.h>
  2. using namespace std;

  4. struct File{
  5.     int fileInfo[5] = {0};
  6. };

  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. };

  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.     }

  46.     vector<int> orders(K);
  47.     for(auto &i:orders)
  48.         cin >> i;
  49.     reverse(orders.begin(), orders.end());

  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);

  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. */
複製代碼




歡迎光臨 種子論壇 | 高雄市資訊培育協會學員討論區 (http://seed.istak.org.tw/) Powered by Discuz! 7.2