每日一题——数据中心网络地址规划

数据中心网络地址规划

问题描述

你是一名数据中心网络地址规划人员。每个业务需要一段IP地址区间，形式为：

起始IP 终止IP

不同业务的地址不能重叠。请你从所有区间中选择一些互不重叠的区间，使得：

1. 选择的区间数量最多；
2. 如果数量相同，选择占用IP地址数最少的方案；
3. 如果仍然相同，则按起始IP的字典序排序（小的优先）。

输入格式

• 第一行是业务个数 $n$（$1\le n\le 1000$）；
• 接下来的 $n$ 行是每个业务的IP地址区间。

输出格式

按规则选出的多个区间，按照排序规则输出，每行一个。

---

示例输入

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. IP地址转换

IP地址用点分十进制表示（如192.168.1.10），我们把它转换为32位整数，方便比较大小与计算长度。

转换公式：
$$IP=a\times 256^3+b\times 256^2+c\times 256+d$$

2. 区间排序

根据以下优先级对区间排序：

• 按结束IP升序；
• 若结束IP相同，则按区间长度升序；
• 若都相同，则按起始IP升序。

3. 动态规划

设 dp[i] 表示前 $i$ 个区间中最优方案，记录：

• 区间数量；
• 总占用IP地址数；
• 字典序；
• 所选区间下标。

我们用动态规划在 O(n^2) 范围内求解最优不重叠区间选择方案。

---

C语言完整实现（含详细注释）

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define MAXN 1005// 将IP地址字符串转换为32位无符号整数
unsigned int ip_to_int(const char *ip) {unsigned int a, b, c, d;sscanf(ip, "%u.%u.%u.%u", &a, &b, &c, &d);return (a << 24) | (b << 16) | (c << 8) | d;
}// 将整数形式的IP转换为字符串格式
void int_to_ip(unsigned int ip, char *out) {sprintf(out, "%u.%u.%u.%u", (ip >> 24) & 255, (ip >> 16) & 255, (ip >> 8) & 255, ip & 255);
}// 区间结构体，记录起止IP及原始字符串
typedef struct {unsigned int start, end;unsigned int cost;  // 占用IP数char s_str[20], e_str[20]; // 原始字符串
} Interval;// 动态规划方案结构体
typedef struct {int cnt;      // 选中业务数量int cost;     // 总占用IP数int index[MAXN]; // 记录选择的区间下标int index_len;
} DPPlan;Interval intervals[MAXN];
DPPlan dp[MAXN];
int p[MAXN]; // p[i]：第i个区间能接在p[i]之后int cmp(const void *a, const void *b) {Interval *x = (Interval *)a;Interval *y = (Interval *)b;if (x->end != y->end) return x->end < y->end ? -1 : 1;if (x->cost != y->cost) return x->cost < y->cost ? -1 : 1;return x->start < y->start ? -1 : 1;
}// 判断 plan1 是否比 plan2 更优
int better(DPPlan *a, DPPlan *b) {if (a->cnt != b->cnt) return a->cnt > b->cnt;if (a->cost != b->cost) return a->cost < b->cost;for (int i = 0; i < a->index_len && i < b->index_len; i++) {unsigned int sa = intervals[a->index[i]].start;unsigned int sb = intervals[b->index[i]].start;if (sa != sb) return sa < sb;}return 1;
}int main() {int n;scanf("%d", &n);// 读取区间for (int i = 0; i < n; i++) {scanf("%s %s", intervals[i].s_str, intervals[i].e_str);intervals[i].start = ip_to_int(intervals[i].s_str);intervals[i].end = ip_to_int(intervals[i].e_str);intervals[i].cost = intervals[i].end - intervals[i].start + 1;}// 按照排序规则排序qsort(intervals, n, sizeof(Interval), cmp);// 二分预处理p[i]：找出与当前区间不重叠的最后一个for (int i = 0; i < n; i++) {p[i] = -1;for (int j = i - 1; j >= 0; j--) {if (intervals[j].end < intervals[i].start) {p[i] = j;break;}}}// 初始化dp[0]dp[0].cnt = 1;dp[0].cost = intervals[0].cost;dp[0].index[0] = 0;dp[0].index_len = 1;for (int i = 1; i < n; i++) {DPPlan pick = {0}, no_pick = dp[i - 1];if (p[i] != -1) {pick = dp[p[i]];  // 从p[i]转移而来}pick.cnt += 1;pick.cost += intervals[i].cost;pick.index[pick.index_len++] = i;if (better(&pick, &no_pick)) {dp[i] = pick;} else {dp[i] = no_pick;}}// 输出最后一个最优方案中的区间for (int i = 0; i < dp[n - 1].index_len; i++) {int idx = dp[n - 1].index[i];printf("%s %s\n", intervals[idx].s_str, intervals[idx].e_str);}return 0;
}

---

总结

• 使用整数形式处理IP地址，便于大小比较；
• 多重排序确保满足题目的优先级要求；
• 动态规划+二分预处理高效求解；
• 所有处理逻辑均添加详细注释，适合C语言学习者参考。