如何将整数对划分问题的算法从二次复杂度优化至对数线性？

问题描述 #

给定n对整数，需将其划分为两个非空子集A和B，目标是最小化「A中首元素的极差（最大值-最小值） + B中次元素的极差（最大值-最小值）」。

示例：n=4，整数对为{0,0}、{5,5}、{1,1}、{3,4}，最优划分是A={{0,0},{1,1}}，B={{5,5},{3,4}}，此时A首元素极差为1-0=1，B次元素极差为5-4=1，总和为2。

现有二次复杂度算法 #

先按首元素从小到大排序数组，遍历所有连续区间作为子集A，剩余元素作为B，计算对应极差和并取最小值。C++代码如下：

int calc(pair<int, int> a[], int n){
    int m = 1e9, M = -1e9, res = 2e9; //m and M are min and max of all the first values in subset A 
    for (int l = 1; l <= n; l++){
        int g = m, G = M; //g and G are min and max of all the second values in subset B
        for(int r = n; r >= l; r--) {
            if (r - l + 1 < n){
                res = min(res, a[r].first - a[l].first + G - g);
            }
            g = min(g, a[r].second);
            G = max(G, a[r].second);
        }
        m = min(m, a[l].second);
        M = max(M, a[l].second);
    }
    return res;
}

该算法时间复杂度为O(n²)，当n较大时效率不足。

O(n log n)优化方案 #

核心前提 #

最优的子集A一定是首元素连续的区间（证明：若A的首元素不连续，将中间缺失的元素加入A，A的首元素极差不变，B的次元素极差不会增大，总和不会变坏）。因此只需考虑所有连续区间作为A的情况。

优化步骤 #

1. 排序数组：将数组按首元素从小到大排序，时间复杂度O(n log n)。
2. 预处理极值数组：计算前缀和后缀的次元素极值，O(n)时间完成：
   • prefix_min[i]：前i+1个元素（索引0到i）的次元素最小值
   • prefix_max[i]：前i+1个元素的次元素最大值
   • suffix_min[i]：从索引i到n-1的元素的次元素最小值
   • suffix_max[i]：从索引i到n-1的元素的次元素最大值
     代码示例：

   vector<int> prefix_min(n), prefix_max(n);
   vector<int> suffix_min(n), suffix_max(n);
   
   // 预处理前缀极值
   prefix_min[0] = a[0].second;
   prefix_max[0] = a[0].second;
   for (int i = 1; i < n; ++i) {
       prefix_min[i] = min(prefix_min[i-1], a[i].second);
       prefix_max[i] = max(prefix_max[i-1], a[i].second);
   }
   
   // 预处理后缀极值
   suffix_min[n-1] = a[n-1].second;
   suffix_max[n-1] = a[n-1].second;
   for (int i = n-2; i >= 0; --i) {
       suffix_min[i] = min(suffix_min[i+1], a[i].second);
       suffix_max[i] = max(suffix_max[i+1], a[i].second);
   }
   

3. 枚举所有有效A区间：分三种情况计算极差和，取最小值，总时间O(n)：
   • A为前缀区间：A是[0, r]（r从0到n-2，保证B非空），B为[r+1, n-1]，总和为a[r].first - a[0].first + (suffix_max[r+1] - suffix_min[r+1])。
   • A为后缀区间：A是[l, n-1]（l从1到n-1，保证B非空），B为[0, l-1]，总和为a[n-1].first - a[l].first + (prefix_max[l-1] - prefix_min[l-1])。
   • A为中间区间：A是[l, r]（0 < l ≤ r < n-1），B为[0,l-1]和[r+1,n-1]，总和为a[r].first - a[l].first + (max(prefix_max[l-1], suffix_max[r+1]) - min(prefix_min[l-1], suffix_min[r+1]))。这里用双指针优化遍历：初始化r = l，遍历每个l从1到n-2，逐步增大r直到总和不再减小，每个r仅被访问一次，总遍历次数为O(n)。

完整优化后代码示例 #

#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int calc_opt(vector<pair<int, int>>& a) {
    int n = a.size();
    if (n < 2) return 0;
    
    // 按首元素排序
    sort(a.begin(), a.end());
    
    // 预处理前缀极值
    vector<int> prefix_min(n), prefix_max(n);
    prefix_min[0] = a[0].second;
    prefix_max[0] = a[0].second;
    for (int i = 1; i < n; ++i) {
        prefix_min[i] = min(prefix_min[i-1], a[i].second);
        prefix_max[i] = max(prefix_max[i-1], a[i].second);
    }
    
    // 预处理后缀极值
    vector<int> suffix_min(n), suffix_max(n);
    suffix_min[n-1] = a[n-1].second;
    suffix_max[n-1] = a[n-1].second;
    for (int i = n-2; i >= 0; --i) {
        suffix_min[i] = min(suffix_min[i+1], a[i].second);
        suffix_max[i] = max(suffix_max[i+1], a[i].second);
    }
    
    int res = INT_MAX;
    
    // 情况1：A是前缀区间[0, r]
    for (int r = 0; r < n-1; ++r) {
        int b_range = suffix_max[r+1] - suffix_min[r+1];
        res = min(res, a[r].first - a[0].first + b_range);
    }
    
    // 情况2：A是后缀区间[l, n-1]
    for (int l = 1; l < n; ++l) {
        int b_range = prefix_max[l-1] - prefix_min[l-1];
        res = min(res, a[n-1].first - a[l].first + b_range);
    }
    
    // 情况3：A是中间区间[l, r]，0 < l ≤ r < n-1
    int r = 1;
    for (int l = 1; l < n-1; ++l) {
        while (r < n-1) {
            int current_sum = a[r].first - a[l].first + 
                              (max(prefix_max[l-1], suffix_max[r+1]) - min(prefix_min[l-1], suffix_min[r+1]));
            int next_sum = a[r+1].first - a[l].first + 
                           (max(prefix_max[l-1], suffix_max[r+2]) - min(prefix_min[l-1], suffix_min[r+2]));
            if (next_sum < current_sum) {
                r++;
            } else {
                break;
            }
        }
        int current_sum = a[r].first - a[l].first + 
                          (max(prefix_max[l-1], suffix_max[r+1]) - min(prefix_min[l-1], suffix_min[r+1]));
        res = min(res, current_sum);
        if (r == l && r < n-2) {
            r++;
        }
    }
    
    return res;
}

复杂度分析 #

• 排序：O(n log n)
• 预处理极值数组：O(n)
• 枚举所有区间：O(n)
  总时间复杂度为O(n log n)，符合要求。

内容的提问来源于stack exchange，提问作者Minh Hien