題目列表

3507. 移除最小數對使數組有序 I
3508. 設計路由器
3509. 最大化交錯和為 K 的子序列乘積
3510. 移除最小數對使數組有序 II

一、移除最小數對使數組有序 I & II

由于數組是給定的，所以本題的操作步驟是固定的，我們只要能快速模擬操作的過程即可
設 $i、j$ 為當前進行了操作之后的一對相鄰元素下標

• 如何快速找到 $nums[i]$ 左右兩邊相鄰的 $nums[l]、nums[r]$

  • 思路一：維護下標的有序集合，當我們進行合并 $nums[i]、nums[j](i<j)$時 ，刪除 $j$，保留 $i$，當我們要查找 $i$ 左右兩邊的相鄰元素時，就去二分查找答案，可以用 $set$ 維護
  • 思路二：用數組模擬雙向鏈表的增刪查改操作，即維護數組 $left[i]、right[i]$，分別記錄 $i$ 左右兩邊的元素下標

• 如何快速的找到和最小的 $nums[i]、nums[j]？$

  • 可以用最小堆記錄 p a i r { n u m s [ i ] + n u m s [ j ] , i } pair\{nums[i]+nums[j],i\} pair{nums[i]+nums[j],i}，這里的 $i$ 為數對下標中較小的那個，即 $i<j$
  • 當我們將 $nums[i]、nums[j]$ 跟新為 $nums[i]+nums[j]$ (記為 $s$)時，不僅需要向堆中添加 { n u m s [ l ] + s , l } 、 { s + n u m s [ r ] , i } \{nums[l]+s,l\}、\{s+nums[r],i\} {nums[l]+s,l}、{s+nums[r],i}，還需要從堆中刪除 { n u m s [ l ] + n u m s [ i ] , l } 、 { n u m s [ i + 1 ] + n u m s [ r ] , j } \{nums[l]+nums[i],l\}、\{nums[i+1]+nums[r],j\} {nums[l]+nums[i],l}、{nums[i+1]+nums[r],j}，需要用到懶刪除的技巧
  • 如果不會懶刪除技巧，可以用有序集合 $set$ 來模擬實現懶刪除堆

代碼如下

// C++
class Solution {
public:int minimumPairRemoval(vector<int>& nums) {int n = nums.size();vector<int> left(n, -1), right(n + 1, n); // 模擬雙向鏈表priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;int cnt = 0; //  記錄 nums[i] > nums[i+1] 的個數，以此來判斷數組是否是非遞減的// 初始化for(int i = 0; i < n; i++){right[i] = i + 1;if(i + 1 < n) {left[i+1] = i;pq.emplace(nums[i] + nums[i+1], i);cnt += nums[i] > nums[i + 1];}}int step = 0;while(cnt > 0){// 懶刪除// right[pq.top().second] >= n 表示當前 pq.top().second 已經被合并后刪除// pq.top().first != nums[pq.top().second] + nums[right[pq.top().second]] 表示 nums[right[pq.top().second]] 已經被合并過了while(right[pq.top().second] >= n || pq.top().first != nums[pq.top().second] + nums[right[pq.top().second]]){pq.pop();}auto [s, i] = pq.top(); pq.pop();int l = left[i], j = right[i], r = right[j]; // l,i,j,r 之間的大小關系發生變化// 由于 i、j 要合并，先去掉之前的大小關系if(nums[i] > nums[j]) cnt--;if(l != -1 && nums[l] > nums[i]) cnt--;if(r != n && nums[j] > nums[r]) cnt--;// 加入新的大小關系if(l != -1 && nums[l] > s) cnt++;if(r != n && s > nums[r]) cnt++;// 如果 i 的前面有數字，則將{nums[l]+s,l}加入堆中if(l != -1){pq.emplace(s + nums[l], l);}// 如果 i 的后面有數字，則將{nums[r]+s,r}加入堆中if(r != n){pq.emplace(s + nums[r], i);}// 刪除 j 結點，保留 i 結點// 讓 i -> r, r -> i// 同時讓 j -> n 表示 結點 j 被刪除if(j < n) right[i] = right[j], right[j] = n;if(r < n) left[r] = i;nums[i] = s; // 跟新當前合并之后的值step++;}return step;}
};

二、設計路由器

本題關鍵理解題意，抽象出我們需要使用的數據結構

• $int[]forwardPacket()$ 需要先進先出：需要有一個 $queue$
• $booladdPacket(intsource,intdestination,inttimestamp)$ 要求不能重復插入相同的數據包：需要一個哈希表 $unordered\_set$，記錄插入過的數據包
• $intgetCount(intdestination,intstartTime,intendTime)$ 獲取尚未轉發的時間在 $[startTime,endTime]$ 中，且目標為 $destination$ 的數據包的個數：這里我們可以把 $destination$ 相同的數據包放在一個數組中，由于數據包是按照時間順序插入的，我們可以用二分法，獲取區間內的數據包個數，即額外維護一個 $unordered\_map<int,vector<int>>$

代碼如下

class Router {unordered_map<int,vector<int>> d_t; // [d, vt]// 這里使用循環數組模擬隊列vector<tuple<int,int,int>> v;int l = 0, r = 0;unordered_set<string> st;
public:Router(int memoryLimit) : v(memoryLimit + 1) {}bool addPacket(int s, int d, int t) {string mask = to_string(s) + '|' +  to_string(d) + '|' + to_string(t);if(st.count(mask)) return false;st.insert(mask);if((r + 1)%v.size() == l){ // 隊列滿auto [ss, dd, tt] = v[l++];l %= v.size();st.erase(to_string(ss) + '|' + to_string(dd) + '|' + to_string(tt));d_t[dd].erase(d_t[dd].begin());}d_t[d].push_back(t);v[r++] = {s, d, t};r %= v.size();return true;}vector<int> forwardPacket() {if(r == l) return {}; // 隊列為空auto [s, d, t] = v[l++];l %= v.size();d_t[d].erase(d_t[d].begin());st.erase(to_string(s) + '|' + to_string(d) + '|' + to_string(t));return {s, d, t};}int getCount(int d, int startTime, int endTime) {auto& v = d_t[d];return ranges::upper_bound(v, endTime) - ranges::lower_bound(v, startTime);}
};

三、最大化交錯和為 K 的子序列乘積

本題只需要暴搜即可，因為狀態的個數并沒有我們想象的那么多

• 狀態定義為 $dfs(i,s,m,op,empty)$

  • $i$ 表示枚舉的數字下標
  • $s$ 表示交錯和
  • $m$ 表示子序列的元素乘積
  • $op$ 表示當前元素是取正，還是取負
  • $empty$ 表示子序列是否為空

• 有人可能覺得這個狀態太多了，肯定會超時
  
  因為 $m$ 的取值范圍是 $[1,5000]$，但實際上，在當前的數據范圍內 $m$ 最多只有 $394+1$ 種可能取值($+1$ 表示當子序列中有 $0$ 時，乘積為 $0$)，可以通過如下代碼進行驗證

int init = [](){set<int> st{1};for(int i = 0; i < 150; i++){ // 150 個值auto tmp = st;for(auto x : st){for(int i = 1; i <= 12; i++){ // 每個值有可以取 1~12if(x * i <= 5000){st.insert(x * i);}}}}cout << st.size() << endl;return 0;
}();

代碼如下

class Solution {
public:int maxProduct(vector<int>& nums, int k, int limit) {int total = reduce(nums.begin(), nums.end());if (total < abs(k)) { // |k| 太大return -1;}int n = nums.size(), ans = -1;unordered_set<long long> vis;auto dfs = [&](this auto&& dfs, int i, int s, int m, bool op, bool empty) -> void {// 無法讓 ans 變得更大// 注意：當 m > limit && ans < 0 時，如果在選擇一個0，既能讓 m < limt，ans = 0if (ans == limit || m > limit && ans >= 0) { return;}if (i == n) {if (!empty && s == k && m <= limit) { // 合法子序列ans = max(ans, m); // 更新答案的最大值}return;}long long mask = (long long) i << 32 | (s + total) << 15 | m << 2 | op << 1 | empty;if (!vis.insert(mask).second) {return;}// 不選 xdfs(i + 1, s, m, op, empty);// 選 xint x = nums[i];dfs(i + 1, s + (op ? -x : x), min(m * x, limit + 1), !op, false);};dfs(0, 0, 1, false, true);return ans;}
};