题解

题面描述

在云化平台中，组件按版本号统一管理，版本号遵循语义化版本控制，格式为：

major.minor.patch

• $major$：重大更新，可能包含向后不兼容的功能。
• $minor$：在向后兼容的前提下新增功能。
• $patch$：在向后兼容的前提下修复错误，没有新增功能。

业务$App$在配置文件中声明其依赖组件及版本，支持如下三种声明方式：

1. *：取仓库中最新版本。
2. ^major[.minor[.patch]]：匹配相同$major$且版本号不低于声明版本的最大版本。
3. -major.minor[.patch] 或 ~major.minor[.patch]：匹配相同 $major$ 和 $minor$ 且版本号不低于声明版本的最大版本（即只更新补丁）。

说明：- 与 ~ 前缀等价，示例中使用 - 时也表示只更新补丁。

版本号缩写

声明时可省略 minor 或 patch，未写出部分默认补齐为$0$，例如：

• 2 等价于 2.0.0
• 1.2 等价于 1.2.0

解题思路

1. 解析版本号声明：

   • 若声明为 *，直接从所有版本中选最大。
   • 若声明以 ^ 开头，解析后缀版本为三元组(major_0,minor_0,patch_0)，保留所有满足 major = major_0 且 版本三元组 >= (major_0,minor_0,patch_0) 的版本。
   • 若声明以 - 或 ~ 开头，解析后缀版本为三元组(major_0,minor_0,patch_0)，保留满足 major = major_0 且 minor = minor_0 且 版本三元组 >= (major_0,minor_0,patch_0) 的版本。

2. 版本号标准化：

   • 按 . 分割字符串，补齐至三元组(major,minor,patch)。

3. 比较规则：

   • 按字典序比较三元组：先比$major$，再比$minor$，最后比$patch$。

4. 遍历筛选：

   • 遍历所有三元组，按声明方式过滤后，记录最大者。

5. 格式化输出：

   • 若无有效版本输出 None。

   • 否则省略尾部 .0：

     • 若 patch = 0，只输出 major.minor；
     • 若 minor = 0 且 patch = 0，只输出 major；
     • 否则输出完整 major.minor.patch。

C++

#include <bits/stdc++.h>
using namespace std;

// 解析版本号，并补齐为三元组
array<int,3> parse(const string &s) {
    array<int,3> v = {0,0,0};
    stringstream ss(s);
    string part;
    int i = 0;
    while (getline(ss, part, '.') && i < 3) {
        v[i++] = stoi(part);
    }
    return v;
}

// 三元组比较，大于返回 true
bool greaterThan(const array<int,3>& a, const array<int,3>& b) {
    return a > b;
}

// 三元组是否 >=
bool atLeast(const array<int,3>& v, const array<int,3>& req) {
    return v >= req;
}

string formatVersion(const array<int,3>& v) {
    if (v[2] == 0) {
        if (v[1] == 0) return to_string(v[0]);
        return to_string(v[0]) + "." + to_string(v[1]);
    }
    return to_string(v[0]) + "." + to_string(v[1]) + "." + to_string(v[2]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<array<int,3>> versions(N);
    string s;
    for (int i = 0; i < N; i++) {
        cin >> s;
        versions[i] = parse(s);
    }
    cin >> s;

    array<int,3> best = {-1,-1,-1};
    if (s == "*") {
        for (auto &v : versions) if (greaterThan(v, best)) best = v;
    } else {
        char mode = s[0];
        auto req = parse(s.substr(1));
        for (auto &v : versions) {
            if (mode == '^') {
                if (v[0] != req[0] || !atLeast(v, req)) continue;
            } else if (mode == '-' || mode == '~') {
                if (v[0] != req[0] || v[1] != req[1] || !atLeast(v, req)) continue;
            }
            if (greaterThan(v, best)) best = v;
        }
    }

    if (best[0] < 0) cout << "None";
    else cout << formatVersion(best);
    return 0;
}

Python

import sys

def parse(s):
    parts = s.split('.')
    return tuple(int(parts[i]) if i < len(parts) else 0 for i in range(3))

def format_version(v):
    major, minor, patch = v
    if patch == 0:
        if minor == 0:
            return f"{major}"
        return f"{major}.{minor}"
    return f"{major}.{minor}.{patch}"

N = int(sys.stdin.readline())
versions = [parse(sys.stdin.readline().strip()) for _ in range(N)]
req = sys.stdin.readline().strip()

best = (-1, -1, -1)

def at_least(v, target):
    return v >= target

if req == '*':
    best = max(versions)
else:
    mode = req[0]
    target = parse(req[1:])
    for v in versions:
        if mode == '^':
            if v[0] != target[0] or not at_least(v, target):
                continue
        if mode in ('-', '~'):
            if v[0] != target[0] or v[1] != target[1] or not at_least(v, target):
                continue
        if v > best:
            best = v

if best[0] < 0:
    print('None')
else:
    print(format_version(best))

Java

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

public class Main {
    private static int[] parse(String s) {
        String[] parts = s.split("\\.");
        int[] v = {0,0,0};
        for (int i = 0; i < parts.length && i < 3; i++) {
            v[i] = Integer.parseInt(parts[i]);
        }
        return v;
    }

    private static String formatVersion(int[] v) {
        if (v[2] == 0) {
            if (v[1] == 0) return String.valueOf(v[0]);
            return v[0] + "." + v[1];
        }
        return v[0] + "." + v[1] + "." + v[2];
    }

    private static int compare(int[] a, int[] b) {
        for (int i = 0; i < 3; i++) if (a[i] != b[i]) return a[i] - b[i];
        return 0;
    }

    private static boolean atLeast(int[] v, int[] req) {
        for (int i = 0; i < 3; i++) {
            if (v[i] < req[i]) return false;
            if (v[i] > req[i]) return true;
        }
        return true;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        List<int[]> versions = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            versions.add(parse(br.readLine()));
        }
        String req = br.readLine();

        int[] best = {-1,-1,-1};
        if (req.equals("*")) {
            for (int[] v : versions) if (compare(v, best) > 0) best = v;
        } else {
            char mode = req.charAt(0);
            int[] target = parse(req.substring(1));
            for (int[] v : versions) {
                if (mode == '^') {
                    if (v[0] != target[0] || !atLeast(v, target)) continue;
                } else if (mode == '-' || mode == '~') {
                    if (v[0] != target[0] || v[1] != target[1] || !atLeast(v, target)) continue;
                }
                if (compare(v, best) > 0) best = v;
            }
        }

        if (best[0] < 0) System.out.println("None");
        else System.out.println(formatVersion(best));
    }
}

题目内容

云化平台对于组件按版本号进行统一管理，版本号遵循语义版本控制系统,格式为:

major.minor.patch

其中

major: 项目进行重大更新，且包含不向后兼容的功能

minor:仅在以向后兼容的方式添加新功能

patch:仅在以向后兼容的方式修复错误，并且没有添加任何新的功能

业务$App$在其配置文件中声明其依赖的组件及版本，如:$1.1.0$

并且版本号可以缩写，没有写出来的部分表示为$0$，如:

对于其依赖的版本号，有三种声明方式:

$1.$指定最新版本

业务$App$的配置方式为: *

它最终会匹配仓库中的最新版本给业务$App$使用。

$1.$取$major$版本一致情况下的最大版本

由于$major$版本之间可能不兼容，指定主版本号，业务$App$的配置方式为:^1.2.0

这样写会尝试匹配主版本号为1的最大版本。

更多样例含义:

1.保证$major$和$minor$版本一致，只取最新的$patch$版本，写法为:

只进行$Bug$修复，只更新$patch$，业务$App$的配置方式为:~1.2.0 或者 -1.2.0

这样写会取$major$版本号为$1、minor$版本$2、patch$版本号最大的版本。

输入描述

第一行给出当前仓库中指定组件的版本数量$N$，后续$N$行给出具体的每一个版本号(注意这里不保证版本号的大小顺序)，最后一行给出业务$App$组件的版本号声明。

$3<=N<=100000$

版本号中的major、minor和patch都满足$0<=yersion<=100000$

输出描述

输出最终匹配到的版本号。

如果没有配置的版本号则输出$None$

样例1

输入

5
1.1.1
2.1
1.2.2
1.2.6
1.3.3
^1.2

输出

1.3.3

说明

对于目标组件，当前在仓库中有$5$个版本，分别为 $1.1.1$ $2.1$ $1.2.2$ $1.2.6$ $1.3.3$

业务$App$声明的组件依赖为^1.2，系统最终为其匹配到的版本为$1.3.3$

样例2

输入

5
1.1.1
2.1
1.2.2
1.2.6
1.3.3
*

输出

2.1

说明

*表示取所有版本中的最高版本，即$2.1$

样例3

输入

5
1.1.1
2.1
1.2.2
1.2.6
1.3.3
-1.2

输出

1.2.6

说明

$-$表示在major.minor不变的情况下取patch最大的版本号，这里 即:$1.2.6$

样例4

输入

6
1.1.1
2.1
1.2.2
1.2.6
1.3.3
1.4
^1.6

输出

None

说明

major版本号为$1$ minor大于等于$6$的版本号不存在，输出$None$