2022 F-公司徵才(難)

may

F-公司徵才
時間限制 4 秒 / 記憶體限制 2 G
一間公司打算徵募一些工程師、清潔工和小丑，其中工程師最多有a席名額、清潔工最多有b席名
額、小丑最多有c名額。而總共有n應徵者前來求職。
在面試結束之後，公司知道每一位應徵者，分別作為工程師、清潔工和小丑時，三份不同工作的實力
高低。而此時公司要選擇，該錄取哪一些應徵者並賦予哪項工作。因為人才短缺，一位應徵者可以錄
取多個職位，但是同時身兼三個職位太過於勞累，所以一位應徵者最多只能錄取兩個職位，換言之，
一位應徵者不能同時為工程師、清潔工和小丑，但可以同時是工程師和清潔工，或其他組合，並且各
占了工程師與清潔工的 席名額。
現在公司的目標為，要選擇錄取那些應徵者，並將實力的總和最大化。
● 輸入說明
第一行有四個正整數n, a, b, c ，分別代表有n位應徵者，要應徵最多a 位工程師最多b 位清潔工與
最多c位小丑。
接下來有n行，第i行有三個整數xi, yi, zi ，代表第i位應徵者，分別作為工程師、清潔工與小丑的
實力。
● 輸出說明
輸出一個整數，代表最大的實力總和。
範例輸入1
3 1 1 1
1 2 3
3 1 2
2 3 1
範例輸出1
9

範例輸入2
3 2 2 2
1 2 3
3 1 2
2 3 1
範例輸出2
15
輸出說明
範例輸出1
選擇第2 位應徵者當工程師
選擇第3 位應徵者當清潔工
選擇第1位應徵者當小丑
實力總和為3 + 3 + 3 = 9
範例輸出2
選擇第 2, 3位應徵者當工程師
選擇第 1, 3位應徵者當清潔工
選擇第 1,2位應徵者當小丑
實力總和為3 + 2 + 2 + 3 + 3 + 2 = 15

may

1. #include <bits/stdc++.h>
   
2. //#include <iostream>
   
3. //#include <vector>
   
4. //#include <algorithm>
   
5. //#include <tuple>
   
6. 
   
7. using namespace std;
   
8. 
   
9. // 應徵者結構體
   
10. struct Applicant {
    
11.     int id, x, y, z;
    
12.     Applicant(int id, int x, int y, int z) : id(id), x(x), y(y), z(z) {}
    
13. };
    
14. 
    
15. // 自訂排序方式 (根據單職位能力排序)
    
16. bool cmpX(const Applicant &a, const Applicant &b) { return a.x > b.x; }
    
17. bool cmpY(const Applicant &a, const Applicant &b) { return a.y > b.y; }
    
18. bool cmpZ(const Applicant &a, const Applicant &b) { return a.z > b.z; }
    
19. 
    
20. int main() {
    
21.     int n, a, b, c;
    
22.     cin >> n >> a >> b >> c;
    
23. 
    
24.     vector<Applicant> applicants;
    
25. 
    
26.     // 讀取輸入資料
    
27.     for (int i = 0; i < n; i++) {
    
28.         int x, y, z;
    
29.         cin >> x >> y >> z;
    
30.         applicants.emplace_back(i, x, y, z);
    
31.     }
    
32. 
    
33.     // 記錄被選中的應徵者
    
34.     vector<bool> selected(n, false);
    
35.     int maxPower = 0;
    
36. 
    
37.     // **Step 1: 選擇最強的工程師**
    
38.     sort(applicants.begin(), applicants.end(), cmpX);
    
39.     for (int i = 0; i < a && i < n; i++) {
    
40.         maxPower += applicants[i].x;
    
41.         selected[applicants[i].id] = true;
    
42.     }
    
43. 
    
44.     // **Step 2: 選擇最強的清潔工**
    
45.     sort(applicants.begin(), applicants.end(), cmpY);
    
46.     int cleanCount = 0;
    
47.     for (int i = 0; i < n && cleanCount < b; i++) {
    
48.         if (!selected[applicants[i].id]) { // 尚未被選為工程師
    
49.             maxPower += applicants[i].y;
    
50.             selected[applicants[i].id] = true;
    
51.             cleanCount++;
    
52.         }
    
53.     }
    
54. 
    
55.     // **Step 3: 選擇最強的小丑**
    
56.     sort(applicants.begin(), applicants.end(), cmpZ);
    
57.     int clownCount = 0;
    
58.     for (int i = 0; i < n && clownCount < c; i++) {
    
59.         if (!selected[applicants[i].id]) { // 尚未被選為工程師或清潔工
    
60.             maxPower += applicants[i].z;
    
61.             clownCount++;
    
62.         }
    
63.     }
    
64. 
    
65.     // **Step 4: 找雙職位的應徵者補充**
    
66.     vector<tuple<int, int, int>> dualOptions; // (應徵者ID, 增加的實力, 類型)
    
67. 
    
68.     for (int i = 0; i < n; i++) {
    
69.         if (!selected[applicants[i].id]) continue;
    
70. 
    
71.         int extraPower = 0;
    
72.         int type = -1;
    
73. 
    
74.         // 這個人已被選擇，但還能補其他職位
    
75.         if (cleanCount < b) {
    
76.             extraPower = applicants[i].y;
    
77.             type = 1; // 增加清潔工
    
78.         }
    
79.         if (clownCount < c && applicants[i].z > extraPower) {
    
80.             extraPower = applicants[i].z;
    
81.             type = 2; // 增加小丑
    
82.         }
    
83. 
    
84.         if (type != -1) {
    
85.             dualOptions.emplace_back(applicants[i].id, extraPower, type);
    
86.         }
    
87.     }
    
88. 
    
89.     // 按額外實力排序，選擇最優解
    
90.     sort(dualOptions.begin(), dualOptions.end(), [](const tuple<int, int, int> &a, const tuple<int, int, int> &b) {
    
91.         return get<1>(a) > get<1>(b);
    
92.     });
    
93. 
    
94.     for (auto &[id, extra, type] : dualOptions) {
    
95.         if (type == 1 && cleanCount < b) { // 增加清潔工
    
96.             maxPower += extra;
    
97.             cleanCount++;
    
98.         } else if (type == 2 && clownCount < c) { // 增加小丑
    
99.             maxPower += extra;
    
100.             clownCount++;
     
101.         }
     
102.     }
     
103. 
     
104.     // **輸出最大總實力**
     
105.     cout << maxPower << endl;
     
106. 
     
107.     return 0;
     
108. }

複製代碼

回復 1# may
----------------------------------------------------------
測資
測試資料00（基本測試）
輸入：
3 1 1 1
1 2 3
3 1 2
2 3 1
預期輸出：

9
解釋：

第 2 位當工程師 (3)

第 3 位當清潔工 (3)

第 1 位當小丑 (3)

測試資料01（所有名額皆可滿足）
輸入：

3 2 2 2
1 2 3
3 1 2
2 3 1
預期輸出：

15
解釋：

第 2、3 位當工程師 (3+2)

第 1、3 位當清潔工 (2+3)

第 1、2 位當小丑 (3+2)

測試資料 02（部分名額不足）
輸入：

4 3 3 3
4 5 6
3 2 1
7 8 9
5 6 7
預期輸出：

42
解釋：

第 3、4、1 位當工程師 (7+5+4)

第 3、4、1 位當清潔工 (8+6+5)

第 3、4、1 位當小丑 (9+7+6)

測試資料 03（應徵者能力有重複值）
輸入：

5 2 2 2
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
預期輸出：

20
解釋：

任意 2 位當工程師 (5+5)

任意 2 位當清潔工 (5+5)

任意 2 位當小丑 (5+5)

測試資料 04（名額小於應徵者數量，需選最強者）
輸入：
6 2 2 2
1 2 3
4 5 6
7 8 9
3 6 9
5 2 1
9 3 2
預期輸出：
38
解釋：

第 6、3 位當工程師 (9+7)

第 3、2 位當清潔工 (8+5)

第 3、4 位當小丑 (9+9)

這些測試資料涵蓋了：

基本情境（測試正確性）。

所有名額皆可滿足（測試最大化選擇）。

部分名額不足（測試名額限制）。

應徵者能力相同（測試公平性）。

名額小於應徵者數量（測試最佳選擇策略）。