202406潛力2-會議室租用MeetingRoom_找不到judge

may

大明經營一間專門租用共享空間的公司，由於需求太過熱門，目前只剩下一間會議室可供出租。已知還有 N 位客戶在等候租用，第 i位客戶需要租用時間ai到 bi（包含 ai和 bi）並會支付 ci元。公司希望在使用會議室的時間不衝突的情況之下選擇一些客戶使得收入最大化。 例如：有N = 3位客戶，需要會議室的時段與支付費用如下表所示。最大化收入的策略為選擇第1和3位客戶，收入為6+3=9元。

輸入格式
第一列有一個正整數 N ( N ≤ 2×105)，表示有 N 位客戶。接下來 N 列，每列有三個正整數 ai, bi, ci ( ai ≤ bi ≤ 106, ci ≤ 104)，兩個正整數之間以一個空白為間
隔，表示第 i 位客戶要從時段 ai到 bi (包含 ai和 bi) 支付 ci元租用會議室。
輸出格式
請輸出一個非負整數，表示最大收入。

評分說明
此題目測資分成四組，每組測資有多筆測試資料，需答對該組所有測試資
料才能獲得該組分數，各組詳細限制如下。
第一組 (20 分)：N ≤ 10。
第二組 (20 分)：所有的 ci = 1。
第三組 (30 分)：N ≤ 103。
第四組 (30 分)：無特別限制。

may

1. //#include <iostream>
   
2. //#include <vector>
   
3. //#include <algorithm>
   
4. #include <bits/stdc++.h>
   
5. using namespace std;
   
6. 
   
7. // 定義結構存儲客戶資料
   
8. struct Customer {
   
9.     int start, end, profit;
   
10. };
    
11. 
    
12. // 比較函數：按結束時間排序
    
13. bool compareByEnd(const Customer &a, const Customer &b) {
    
14.     return a.end < b.end;
    
15. }
    
16. 
    
17. // 二分搜尋：找到不重疊的最後一個客戶
    
18. int findLastNonConflict(const vector<Customer> &customers, int index) {
    
19.     int low = 0, high = index - 1;
    
20.     while (low <= high) {
    
21.         int mid = (low + high) / 2;
    
22.         if (customers[mid].end < customers[index].start) {
    
23.             if (customers[mid + 1].end < customers[index].start) {
    
24.                 low = mid + 1;
    
25.             } else {
    
26.                 return mid;
    
27.             }
    
28.         } else {
    
29.             high = mid - 1;
    
30.         }
    
31.     }
    
32.     return -1;
    
33. }
    
34. 
    
35. int main() {
    
36.     int N;
    
37.     cin >> N;
    
38. 
    
39.     vector<Customer> customers(N);
    
40.     for (int i = 0; i < N; ++i) {
    
41.         cin >> customers[i].start >> customers[i].end >> customers[i].profit;
    
42.     }
    
43. 
    
44.     // 按結束時間排序
    
45.     sort(customers.begin(), customers.end(), compareByEnd);
    
46. 
    
47.     // 動態規劃陣列
    
48.     vector<long long> dp(N);
    
49.     dp[0] = customers[0].profit;
    
50. 
    
51.     for (int i = 1; i < N; ++i) {
    
52.         // 包含當前客戶的收益
    
53.         long long includeProfit = customers[i].profit;
    
54.         int last = findLastNonConflict(customers, i);
    
55.         if (last != -1) {
    
56.             includeProfit += dp[last];
    
57.         }
    
58. 
    
59.         // 不包含當前客戶的收益
    
60.         dp[i] = max(dp[i - 1], includeProfit);
    
61.     }
    
62. 
    
63.     // 輸出最大收益
    
64.     cout << dp[N - 1] << endl;
    
65. 
    
66.     return 0;
    
67. }
    
68. /*
    
69. 輸入：
    
70. 3
    
71. 1 4 6
    
72. 2 7 8
    
73. 5 6 3
    
74. 輸出：
    
75. 9
    
76. --------
    
77. 6
    
78. 2 3 3
    
79. 3 4 2
    
80. 4 5 2
    
81. 6 7 3
    
82. 2 6 8
    
83. 1 4 6
    
84. 
    
85. */

複製代碼

--------------------------------------------------------
先備知識:1.struct 2.vector 3.vector排序 4.二分搜  5動態規劃
程式解釋
輸入處理：
讀取客戶數量 N 和每位客戶的租用時間及收益。
排序：
根據每位客戶的結束時間 bi 對客戶進行排序。
二分搜尋：
使用 findLastNonConflict 找到對應客戶中不與當前客戶重疊的最後一個客戶。
動態規劃：
計算包含或不包含當前客戶的收益，並取兩者的最大值。
輸出結果：
最終結果即為 dp[N-1]，即最大收益。
時間複雜度
排序：

may

1. #include<cstdio>
   
2. #include<cstring>
   
3. #include<vector>
   
4. #include<algorithm>
   
5. using namespace std;
   
6. const int N = 200000 + 5;
   
7. 
   
8. struct Case {
   
9.         int l, r, w;
   
10. };
    
11. 
    
12. int solve(int n, const int l[N], const int r[N], const int w[N])
    
13. {
    
14.         static Case v[N];
    
15.         static int dp[N];
    
16.        
    
17.         for (int i = 0; i < n; ++i)
    
18.         {
    
19.                 v[i] = (Case){l[i], r[i], w[i]};
    
20.         }
    
21.         sort(v, v + n, [](const auto& lhs, const auto& rhs) {
    
22.                 return lhs.r < rhs.r;
    
23.         });
    
24.         dp[0] = v[0].w;
    
25.         for (int i = 1; i < n; ++i)
    
26.         {
    
27.                 int cur;
    
28.                 int pos = lower_bound(v, v + i, (Case){0, v[i].l, 0}, [](const auto& lhs, const auto& rhs) {
    
29.                         return lhs.r < rhs.r;
    
30.                 }) - v - 1;
    
31.                
    
32.                 if (pos < 0)
    
33.                 {
    
34.                         cur = v[i].w;
    
35.                 }
    
36.                 else
    
37.                 {
    
38.                         cur = dp[pos] + v[i].w;
    
39.                 }
    
40.                 dp[i] = max(dp[i - 1], cur);
    
41.         }
    
42.         return dp[n - 1];
    
43. }
    
44. 
    
45. int main()
    
46. {
    
47.         int n;
    
48.         static int l[N], r[N], w[N];
    
49.         scanf("%d", &n);
    
50.         for (int i = 0; i < n; ++i)
    
51.         {
    
52.                 scanf("%d%d%d", &l[i], &r[i], &w[i]);
    
53.         }
    
54.         printf("%d\n", solve(n, l, r, w));
    
55.         return 0;
    
56. }

複製代碼