题解

题面描述

给定 $N$ 个业务，每个业务需要的 IP 地址范围是一个闭区间 $[start_{ip}, end_{ip}]$，其中 $start_{ip}$ 表示起始 IP，$end_{ip}$ 表示终止 IP，并且满足 $end_{ip} \geq start_{ip}$。由于不同业务的 IP 地址不能重叠，需要从这些业务中选出一些不重叠的区间，使得满足的业务数量最多。在满足业务数量最多的前提下，选出占用 IP 地址数量最少的方案；如果业务数量和 IP 地址占用数量均相同，则按照选中区间中各业务 $start_{ip}$ 的字典序排序，起始 IP 较小者优先。

输入格式：

• 第一行输入一个整数 $N$，其中 $1 \leq N \leq 1000$。
• 接下来 $N$ 行，每行输入一个 IP 区间，格式为 $start_{ip}\ end_{ip}$，其中 $start_{ip}$ 和 $end_{ip}$ 为合法的 IPv4 地址。

输出格式：

• 输出排序好的若干个 IP 区间，每个区间占一行，格式为 $start_{ip}\ end_{ip}$。

思路

1. IP 地址转换
   将每个 IP 地址转换为 $32$ 位整数，这样便于比较大小和计算区间长度。区间长度的计算公式为

   $$cost = end_{ip} - start_{ip} + 1$$

2. 区间排序
   按照以下规则对区间进行排序：

   • 首先按照 $end_{ip}$ 升序排序。
   • 若 $end_{ip}$ 相同，则按照区间长度 $cost$ 升序排序。
   • 若上面两者都相同，则按照 $start_{ip}$ 升序排序。

3. 预处理非重叠区间
   对于每个区间 $i$，利用二分查找找到最大的下标 $j$，使得区间 $j$ 的 $end_{ip}$ 小于区间 $i$ 的 $start_{ip}$，记为 $p(i)$。

4. 动态规划
   设 $dp[i]$ 表示在前 $i$ 个区间中能够获得的最优方案，每个方案包括：

   • 选中的业务数量（尽可能多）
   • 总的 IP 地址占用数（尽可能少）
   • 按选中区间中各业务 $start_{ip}$ 的字典序（起始 IP 较小者优先）

   对于每个区间 $i$，有两种选择：

   • 不选区间 $i$：则方案继承自 $dp[i-1]$。
   • 选择区间 $i$：则方案为 $dp[p(i)]$ 加上当前区间 $i$，此时业务数量加 $1$，IP 占用数增加当前区间的 $cost$，并将当前区间的 $start_{ip}$ 加入字典序列表中。

   最后比较两种方案，选择更优的一个更新 $dp[i]$。

5. 输出结果
   输出 $dp[N-1]$ 中保存的区间，按照原始输入格式输出。

综上，通过预处理非重叠区间信息并结合动态规划，可以选出满足最多业务、占用 IP 地址最少且字典序最优的方案。

cpp

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <cstdio>
#include <algorithm>
using namespace std;
// 将IP地址字符串转换为无符号整数
unsigned int ipToInt(const string &ip) {
    unsigned int a, b, c, d;
    sscanf(ip.c_str(), "%u.%u.%u.%u", &a, &b, &c, &d);
    return ((a << 24) | (b << 16) | (c << 8) | d);
}
// 将无符号整数转换为IP地址字符串
string intToIp(unsigned int ipInt) {
    return to_string((ipInt >> 24) & 0xFF) + "." + 
           to_string((ipInt >> 16) & 0xFF) + "." + 
           to_string((ipInt >> 8) & 0xFF) + "." + 
           to_string(ipInt & 0xFF);
}
// 业务区间结构体
struct Interval {
    unsigned int start, end; // 转换后的起始和结束IP（整数形式）
    unsigned int cost;       // IP占用数：end - start + 1
    string s_str, e_str;     // 原始起始和结束IP字符串
};
// 记录 DP 状态的结构体
struct Result {
    int cnt;                 // 选择的区间数
    unsigned long long cost; // 总 IP 占用数
    vector<unsigned int> lex; // 方案中各区间的起始IP（用于字典序比较）
    vector<int> idx;         // 选中的区间在排序后数组中的下标（用于输出）
};
// 自定义比较函数：比较两个 DP 结果，返回 true 表示 a 更优
bool better(const Result &a, const Result &b) {
    if(a.cnt != b.cnt) return a.cnt > b.cnt;          // 业务数越多越好
    if(a.cost != b.cost) return a.cost < b.cost;          // IP占用越少越好
    // 字典序比较：逐个比较起始IP
    for (size_t i = 0; i < a.lex.size(); i++) {
        if(a.lex[i] != b.lex[i])
            return a.lex[i] < b.lex[i];                 // 起始IP较小者优先
    }
    return true; // 完全相同时，任意认为 a 更优
}
int main(){
    int n;
    cin >> n;
    vector<Interval> intervals(n);
    // 读取输入
    for (int i = 0; i < n; i++){
        string start_ip, end_ip;
        cin >> start_ip >> end_ip;
        intervals[i].s_str = start_ip;
        intervals[i].e_str = end_ip;
        intervals[i].start = ipToInt(start_ip);
        intervals[i].end = ipToInt(end_ip);
        intervals[i].cost = intervals[i].end - intervals[i].start + 1;
    }
    // 排序规则：按结束IP升序；若结束相同，则按区间长度（cost）升序；再按起始IP升序
    sort(intervals.begin(), intervals.end(), [](const Interval &a, const Interval &b) {
        if(a.end != b.end) return a.end < b.end;
        if(a.cost != b.cost) return a.cost < b.cost;
        return a.start < b.start;
    });
    // 预处理 p 数组：对于每个 i，找到最大的 j < i 使得 intervals[j].end < intervals[i].start
    vector<int> p(n, -1);
    for (int i = 0; i < n; i++){
        int lo = 0, hi = i - 1, pos = -1;
        while(lo <= hi){
            int mid = (lo + hi) / 2;
            if(intervals[mid].end < intervals[i].start){
                pos = mid;
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        p[i] = pos;
    }
    // dp[i] 表示考虑前 i 个区间（按照排序顺序，i 从 0 到 n-1）的最优结果
    // 为方便 dp 使用，令 dp[-1] 为初始空方案
    vector<Result> dp(n);
    // 处理第0个区间
    Result init;
    init.cnt = 1;
    init.cost = intervals[0].cost;
    init.lex.push_back(intervals[0].start);
    init.idx.push_back(0);
    dp[0] = init;
    // 记录 dp 的最佳方案（在 dp[i] 与不选当前区间时需要比较）
    // 使用一个辅助变量 prev[i] 表示 dp[0...i] 的最优解
    vector<Result> best_dp(n);
    best_dp[0] = dp[0];
    // 从第1个区间开始DP
    for (int i = 1; i < n; i++){
        // 选当前区间 i 的候选方案：先从 p[i] 的最优方案延伸
        Result candidate;
        if(p[i] != -1) {
            candidate = best_dp[p[i]]; // 选取 p[i] 的方案
        } else {
            candidate.cnt = 0;
            candidate.cost = 0;
            candidate.lex.clear();
            candidate.idx.clear();
        }
        // 加上当前区间
        candidate.cnt += 1;
        candidate.cost += intervals[i].cost;
        candidate.lex.push_back(intervals[i].start);
        candidate.idx.push_back(i);
        // 另一个方案是不选当前区间，即 best_dp[i-1]
        Result noPick = best_dp[i-1];
        
        // dp[i] 取二者中更优的方案
        if(better(candidate, noPick))
            dp[i] = candidate;
        else
            dp[i] = noPick;
        
        best_dp[i] = dp[i];
    }
    // 最优方案在 best_dp[n-1] 中
    Result ans = best_dp[n-1];
    
    // 输出选择的区间，按照原来的字符串格式输出
    for (int index : ans.idx) {
        cout << intervals[index].s_str << " " << intervals[index].e_str << "\n";
    }
    
    return 0;
}

python

import sys


# 将IP地址转换为整数，便于比较
def ip_to_int(ip):
    a, b, c, d = map(int, ip.split('.'))
    return (a << 24) | (b << 16) | (c << 8) | d


# 定义区间类
class Interval:
    def __init__(self, start_str, end_str):
        self.s_str = start_str  # 原始起始IP字符串
        self.e_str = end_str  # 原始结束IP字符串
        self.start = ip_to_int(start_str)
        self.end = ip_to_int(end_str)
        self.cost = self.end - self.start + 1  # IP占用数


# 比较两个DP方案的好坏
def better(a, b):
    # a、b为字典，分别记录了方案的业务数（cnt）、总IP占用（cost）、各区间起始IP（lex）和选择的区间下标（indices）
    if a['cnt'] != b['cnt']:
        return a['cnt'] > b['cnt']  # 业务数越多越好
    if a['cost'] != b['cost']:
        return a['cost'] < b['cost']  # IP占用越少越好
    # 按字典序比较各区间的起始IP
    for x, y in zip(a['lex'], b['lex']):
        if x != y:
            return x < y
    return True


# 主函数
def main():
    n = int(sys.stdin.readline().strip())
    intervals = []
    for _ in range(n):
        parts = sys.stdin.readline().strip().split()
        intervals.append(Interval(parts[0], parts[1]))

    # 按结束IP、区间长度和起始IP升序排序
    intervals.sort(key=lambda inter: (inter.end, inter.cost, inter.start))

    # 预处理：对于每个i，找到最大的 j < i，使得 intervals[j].end < intervals[i].start
    p = [-1] * n
    for i in range(n):
        lo, hi, pos = 0, i - 1, -1
        while lo <= hi:
            mid = (lo + hi) // 2
            if intervals[mid].end < intervals[i].start:
                pos = mid
                lo = mid + 1
            else:
                hi = mid - 1
        p[i] = pos

    # dp[i]记录前i个区间（排序后的）中最优的方案，方案由业务数、总IP占用、字典序和选择的区间下标构成
    dp = [None] * n
    best_dp = [None] * n
    # 初始状态：选择第0个区间
    init = {'cnt': 1, 'cost': intervals[0].cost, 'lex': [intervals[0].start], 'indices': [0]}
    dp[0] = init
    best_dp[0] = init

    for i in range(1, n):
        if p[i] != -1:
            candidate = {
                'cnt': best_dp[p[i]]['cnt'] + 1,
                'cost': best_dp[p[i]]['cost'] + intervals[i].cost,
                'lex': best_dp[p[i]]['lex'][:] + [intervals[i].start],
                'indices': best_dp[p[i]]['indices'][:] + [i]
            }
        else:
            candidate = {'cnt': 1, 'cost': intervals[i].cost, 'lex': [intervals[i].start], 'indices': [i]}
        no_pick = best_dp[i - 1]
        dp[i] = candidate if better(candidate, no_pick) else no_pick
        best_dp[i] = dp[i]

    # 输出最终方案中选择的区间（原始字符串格式）
    ans = best_dp[n - 1]
    for idx in ans['indices']:
        print(intervals[idx].s_str, intervals[idx].e_str)


if __name__ == '__main__':
    main()

java

import java.io.*;
import java.util.*;

// 主类
public class Main {
    // 定义区间类
    static class Interval {
        long start, end;    // 转换后的起始和结束IP（整数形式）
        long cost;          // IP占用数：end - start + 1
        String sStr, eStr;  // 原始起始和结束IP字符串

        public Interval(String sStr, String eStr) {
            this.sStr = sStr;
            this.eStr = eStr;
            this.start = ipToInt(sStr);
            this.end = ipToInt(eStr);
            this.cost = end - start + 1;
        }
    }

    // 定义DP状态类，用于记录方案
    static class Result {
        int cnt;                    // 业务数量
        long cost;                  // 总IP占用数
        ArrayList<Long> lex;        // 方案中各区间的起始IP列表，用于字典序比较
        ArrayList<Integer> indices; // 选中的区间在排序数组中的下标

        public Result() {
            cnt = 0;
            cost = 0;
            lex = new ArrayList<>();
            indices = new ArrayList<>();
        }

        // 拷贝构造函数
        public Result(Result other) {
            this.cnt = other.cnt;
            this.cost = other.cost;
            this.lex = new ArrayList<>(other.lex);
            this.indices = new ArrayList<>(other.indices);
        }
    }

    // 将IP地址字符串转换为整数
    static long ipToInt(String ip) {
        String[] parts = ip.split("\\.");
        long a = Long.parseLong(parts[0]);
        long b = Long.parseLong(parts[1]);
        long c = Long.parseLong(parts[2]);
        long d = Long.parseLong(parts[3]);
        return (a << 24) | (b << 16) | (c << 8) | d;
    }

    // 比较两个DP方案，返回true表示a更优
    static boolean better(Result a, Result b) {
        if (a.cnt != b.cnt)
            return a.cnt > b.cnt; // 业务数越多越好
        if (a.cost != b.cost)
            return a.cost < b.cost; // IP占用越少越好
        // 字典序比较各区间的起始IP
        for (int i = 0; i < Math.min(a.lex.size(), b.lex.size()); i++) {
            if (!a.lex.get(i).equals(b.lex.get(i))) {
                return a.lex.get(i) < b.lex.get(i);
            }
        }
        return true;
    }

    public static void main(String[] args) throws Exception {
        // 输入读取
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        Interval[] intervals = new Interval[n];
        for (int i = 0; i < n; i++) {
            String[] parts = br.readLine().split(" ");
            intervals[i] = new Interval(parts[0], parts[1]);
        }

        // 按结束IP、区间长度和起始IP升序排序
        Arrays.sort(intervals, new Comparator<Interval>() {
            public int compare(Interval a, Interval b) {
                if (a.end != b.end)
                    return Long.compare(a.end, b.end);
                if (a.cost != b.cost)
                    return Long.compare(a.cost, b.cost);
                return Long.compare(a.start, b.start);
            }
        });

        // 预处理 p 数组：对于每个 i，找到最大的 j < i，使得 intervals[j].end < intervals[i].start
        int[] p = new int[n];
        Arrays.fill(p, -1);
        for (int i = 0; i < n; i++) {
            int lo = 0, hi = i - 1, pos = -1;
            while (lo <= hi) {
                int mid = (lo + hi) / 2;
                if (intervals[mid].end < intervals[i].start) {
                    pos = mid;
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
            p[i] = pos;
        }

        // dp[i]表示前i个区间中最优的方案，方案由业务数、IP占用、字典序和选择的区间下标构成
        Result[] dp = new Result[n];
        Result[] best_dp = new Result[n];

        // 初始化：选择第0个区间
        Result init = new Result();
        init.cnt = 1;
        init.cost = intervals[0].cost;
        init.lex.add(intervals[0].start);
        init.indices.add(0);
        dp[0] = init;
        best_dp[0] = init;

        for (int i = 1; i < n; i++) {
            Result candidate;
            if (p[i] != -1) {
                candidate = new Result(best_dp[p[i]]);
                candidate.cnt += 1;
                candidate.cost += intervals[i].cost;
                candidate.lex.add(intervals[i].start);
                candidate.indices.add(i);
            } else {
                candidate = new Result();
                candidate.cnt = 1;
                candidate.cost = intervals[i].cost;
                candidate.lex.add(intervals[i].start);
                candidate.indices.add(i);
            }
            Result noPick = best_dp[i - 1];
            dp[i] = better(candidate, noPick) ? candidate : noPick;
            best_dp[i] = dp[i];
        }

        // 输出最终选择的区间，格式与输入相同
        Result ans = best_dp[n - 1];
        for (int index : ans.indices) {
            System.out.println(intervals[index].sStr + " " + intervals[index].eStr);
        }
    }
}

题目内容

你作为数据中心网络地址规划人员，需要尽可能满足不同业务的网络地址需求。每个业务需要的地址范围为一个闭区间 [start_ip,end_ip] 表示，其中 start_ip是起始 $IP$ 地址，end_ip 是终止 $IP$ 地址，end_ip 大于等于 start_ip。

不同业务的 $IP$ 地址不能重叠，因此你需要将业务地址需求，按照一定规则排序，让数据中心网络地址规划尽可能满足更多数量的业务需求。当业多数量相同时，以 $IP$ 地址占用最少优先。当业务数量和 $IP$ 地址占用数量相同时，按照 $IP$ 范围顺序，比较起始 $IP$ 地址，起始地址最小者优先。

输入描述

1.第一行为业务个数 $N$ ，有效范围为 $[1,1000]$

2.输入 $N$ 行 $IP$ 地址区间，其中每个区间的格式为 start_ip end_ip (中间用空格分隔)，其中 start_ip 和 end_ip 为合法的 $IPv4$ 地址点分十进制格式，即 $A,B,C,D$ ，其中 $A、B、C$ 和 $D$ 的取值范围为 $[0,255]$ 。

3.$IP$ 地址大小的比较，是按照 $A、B、C$ 和 $D$ 的顺序进行比较。

输出描述

输出排序好的 $M$ 个 $IP$ 区间，每行一个。每个区间的格式为 start_ip end_ip , 中间用空格分隔。

样例1

输入

3
192.168.1.9 192.168.1.12
192.168.1.1 192.168.1.10
192.168.1.12 192.168.1.13

输出

192.168.1.1 192.168.1.10
192.168.1.12 192.168.1.13

说明

区间 1(192.168.1.9 192.168.1.12) 与区间 2(192.168.1.1 192.168.1.10)和 区间 3(192.168.1.12.192.168.1.13)均有重叠。

因此可规划的业务地址范围为区间 1(192.168.1.1 192.168.1.10) 和 (192.168.1.12 192.168.1.13)，其满足的业务数量最多。

样例2

输入

4
192.168.1.9 192.168.1.12
192.168.1.13 192.168.1.15
192.168.1.7 192.168.1.10
192.168.1.11 192.168.1.17

输出

192.168.1.7 192.168.1.10
192.168.1.13 192.168.1.15

说明

共有 $3$ 种方案，都是两个业务：

1. 192.168.1.7 192.168.1.10 和 192.168.1.13 192.168.1.15

2. 192.168.1.7 192.168.1.10 和 192.168.1.11 192.168.1.17

3. 192.168.1.9 192.168.1.12 和 192.168.1.13 192.168.1.15

方案 $1$ 占用 $7$ 个 $IP$ ，方案 $2$ 占用 $11$ 个 $IP$ ，方案 $3$ 占用 $7$ 个 $IP$ 。从 $IP$ 占用数量上，方案 $2$ 被放弃。

方案 $1$ 和方案 $3$ 对比，第一个业务区间，方案 $1$ 的起始 $IP$ 比方案 $3$ 的起始 $IP$ 小，因此选择方案 $1$ 。