E-VLAN资源池(100p)

VLAN资源池

问题描述

VLAN（虚拟局域网）是一种对局域网设备进行逻辑划分的技术。为了标识不同的 VLAN，引入了 VLAN ID 的概念，它是一个介于 1 到 4094 之间的整数。

我们定义一个 VLAN ID 的资源池（简称 VLAN 资源池）。在这个资源池中，连续的 VLAN ID 用"开始VLAN-结束VLAN"的格式表示，不连续的用单个整数表示。所有的 VLAN ID 用英文逗号连接起来。

现在，给定一个 VLAN 资源池和一个业务需要申请的 VLAN ID，请你输出从 VLAN 资源池中移除申请的 VLAN ID 后的资源池。

输入格式

输入包含两行：

• 第一行是一个字符串，表示 VLAN 资源池。
• 第二行是一个整数，表示业务要申请的 VLAN ID。

输出格式

输出一行字符串，表示从输入的 VLAN 资源池中移除申请的 VLAN ID 后的资源池。输出要求如下：

1. 满足题目描述中的格式。
2. 按照 VLAN ID 从小到大升序输出。
3. 如果申请的 VLAN ID 不在原 VLAN 资源池内，输出原 VLAN 资源池升序排序后的字符串。

样例输入1

1-5
2

样例输出1

1,3-5

样例输入2

20-21,15,18,30,5-10
15

样例输出2

5-10,18,20-21,30

样例输入3

5,1-3
10

样例输出3

1-3,5

样例解释

数据范围

• VLAN ID 的取值范围为 之间的整数。
• 输入 VLAN 资源池中 VLAN 的数量取值范围为 之间的整数。
• 资源池中 VLAN 不重复且合法（ 之间的整数）。
• 输入的 VLAN 资源池是乱序的。

题解

模拟

这道题目的核心在于如何处理 VLAN 资源池的表示和操作。解题思路如下：

1. 解析输入： 首先需要将输入的 VLAN 资源池字符串解析成一个易于操作的数据结构。一个好的选择是使用一个二维数组或列表，其中每个元素代表一个 VLAN 范围。例如，"1-5,7,10-12" 可以解析为 [[1,5], [7,7], [10,12]]。

2. 排序： 将解析后的 VLAN 范围按照起始 VLAN ID 排序。这一步确保了后续操作的正确性和输出的有序性。

3. 移除申请的 VLAN ID： 遍历排序后的 VLAN 范围，找到包含申请 VLAN ID 的范围，并进行相应的调整。这里需要考虑几种情况：

   • 申请的 VLAN ID 是范围的起始值
   • 申请的 VLAN ID 是范围的结束值
   • 申请的 VLAN ID 在范围中间
   • 申请的 VLAN ID 不在任何范围内

4. 合并相邻范围： 移除操作可能导致原本不相邻的范围变得相邻。需要检查并合并这些相邻的范围。

5. 格式化输出： 最后，将处理后的 VLAN 范围转换回题目要求的字符串格式。

参考代码

• Python

def parse_vlan_pool(pool):
    """解析VLAN资源池字符串为列表"""
    ranges = []
    for part in pool.split(','):
        if '-' in part:
            start, end = map(int, part.split('-'))
            ranges.append([start, end])
        else:
            num = int(part)
            ranges.append([num, num])
    return sorted(ranges)  # 按起始VLAN ID排序

def remove_vlan(ranges, vlan):
    """从VLAN范围列表中移除指定的VLAN ID"""
    result = []
    removed = False
    for start, end in ranges:
        if start <= vlan <= end:
            removed = True
            if start < vlan:
                result.append([start, vlan - 1])
            if vlan < end:
                result.append([vlan + 1, end])
        else:
            result.append([start, end])
    return result if removed else ranges

def merge_ranges(ranges):
    """合并相邻的VLAN范围"""
    merged = []
    for range in ranges:
        if not merged or merged[-1][1] + 1 < range[0]:
            merged.append(range)
        else:
            merged[-1][1] = max(merged[-1][1], range[1])
    return merged

def format_output(ranges):
    """格式化VLAN范围列表为输出字符串"""
    return ','.join(f"{start}-{end}" if start != end else str(start) for start, end in ranges)

def main():
    # 读取输入
    pool = input().strip()
    vlan = int(input().strip())

    # 处理VLAN资源池
    ranges = parse_vlan_pool(pool)
    ranges = remove_vlan(ranges, vlan)
    ranges = merge_ranges(ranges)

    # 输出结果
    print(format_output(ranges))

if __name__ == "__main__":
    main()

• C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_RANGES 4094
#define MAX_INPUT 10000

typedef struct {
    int start;
    int end;
} VLANRange;

int compare(const void* a, const void* b) {
    return ((VLANRange*)a)->start - ((VLANRange*)b)->start;
}

int parseVLANPool(char* pool, VLANRange* ranges) {
    int count = 0;
    char* token = strtok(pool, ",");
    while (token != NULL) {
        if (strchr(token, '-') != NULL) {
            sscanf(token, "%d-%d", &ranges[count].start, &ranges[count].end);
        } else {
            ranges[count].start = ranges[count].end = atoi(token);
        }
        count++;
        token = strtok(NULL, ",");
    }
    qsort(ranges, count, sizeof(VLANRange), compare);
    return count;
}

int removeVLAN(VLANRange* ranges, int count, int vlan, VLANRange* result) {
    int resultCount = 0;
    int removed = 0;
    for (int i = 0; i < count; i++) {
        if (ranges[i].start <= vlan && vlan <= ranges[i].end) {
            removed = 1;
            if (ranges[i].start < vlan) {
                result[resultCount].start = ranges[i].start;
                result[resultCount].end = vlan - 1;
                resultCount++;
            }
            if (vlan < ranges[i].end) {
                result[resultCount].start = vlan + 1;
                result[resultCount].end = ranges[i].end;
                resultCount++;
            }
        } else {
            result[resultCount] = ranges[i];
            resultCount++;
        }
    }
    return removed ? resultCount : count;
}

int mergeRanges(VLANRange* ranges, int count) {
    int mergedCount = 0;
    for (int i = 0; i < count; i++) {
        if (i == 0 || ranges[i].start > ranges[mergedCount-1].end + 1) {
            ranges[mergedCount] = ranges[i];
            mergedCount++;
        } else {
            ranges[mergedCount-1].end = ranges[i].end > ranges[mergedCount-1].end ? r