题目链接

讨厌鬼的区间

题目描述

给定三个区间 。

讨厌鬼和小甜妹需要从中选择两个不同的区间。

然后，讨厌鬼从他选择的区间内选一个数 ，小甜妹从她选择的区间内选一个数 。

要求他们选择的数也必须同时在对方的区间内。

目标是使这两个数的和 尽可能大。

请输出这个和的最大值。若不存在这样的数，则输出 -1。

解题思路

1. 简化选择数的条件

设讨厌鬼选择的区间为 ，小甜妹选择的区间为 。

讨厌鬼选择的数是 ，小甜妹选择的数是 。

题目要求 也必须在 内，同时 也必须在 内。

这意味着 必须同时属于 和 ，即 。

同理， 也必须同时属于 和 ，即 。

所以，问题的核心条件可以简化为：讨厌鬼和小甜妹都必须从他们所选的两个区间的交集（Intersection）中选择数字。

2. 最大化和的策略

假设两个选定的区间 和 的交集是一个有效的区间 （其中 且 ，并且 ）。

我们需要从这个交集区间 中选出两个数 和 （ 和 可以相等），使得它们的和 最大。

为了使和最大，我们应该给 和 都赋上该区间内可能的最大值，即 。

所以，对于这一对区间，能得到的最大和就是 。

3. 枚举所有可能的区间组合

题目中给出了三个区间 。讨厌鬼和小甜妹需要选择两个不同的区间，因此总共有三种可能的组合：

  1. 和
  2. 和
  3. 和

我们的算法就是分别计算这三种组合下的最大和，然后取其中的最大值作为最终答案。

4. 算法步骤

  1. 初始化一个变量 max_sum 为 -1，用来记录全局的最大和。

  2. 对于 () 组合：

    • 计算交集的右端点 。
    • 计算交集的左端点 。
    • 如果 （表示交集非空），则计算出这对组合的最大和 ，并更新 。

  3. 对 () 和 () 组合重复上述步骤。

  4. 最后 max_sum 的值就是问题的答案。如果没有任何一对区间的交集是非空的，max_sum 将保持其初始值 -1。

代码

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long l1, r1, l2, r2, l3, r3;
    cin >> l1 >> r1 >> l2 >> r2 >> l3 >> r3;

    long long max_sum = -1;

    // Pair 1: [l1, r1] and [l2, r2]
    long long cur_l = max(l1, l2);
    long long cur_r = min(r1, r2);
    if (cur_l <= cur_r) {
        max_sum = max(max_sum, 2 * cur_r);
    }

    // Pair 2: [l1, r1] and [l3, r3]
    cur_l = max(l1, l3);
    cur_r = min(r1, r3);
    if (cur_l <= cur_r) {
        max_sum = max(max_sum, 2 * cur_r);
    }

    // Pair 3: [l2, r2] and [l3, r3]
    cur_l = max(l2, l3);
    cur_r = min(r2, r3);
    if (cur_l <= cur_r) {
        max_sum = max(max_sum, 2 * cur_r);
    }

    cout << max_sum << endl;

    return 0;
}

import java.util.Scanner;
import java.lang.Math;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long l1 = sc.nextLong();
        long r1 = sc.nextLong();
        long l2 = sc.nextLong();
        long r2 = sc.nextLong();
        long l3 = sc.nextLong();
        long r3 = sc.nextLong();

        long maxSum = -1;

        // Pair 1: [l1, r1] and [l2, r2]
        long curL = Math.max(l1, l2);
        long curR = Math.min(r1, r2);
        if (curL <= curR) {
            maxSum = Math.max(maxSum, 2 * curR);
        }

        // Pair 2: [l1, r1] and [l3, r3]
        curL = Math.max(l1, l3);
        curR = Math.min(r1, r3);
        if (curL <= curR) {
            maxSum = Math.max(maxSum, 2 * curR);
        }

        // Pair 3: [l2, r2] and [l3, r3]
        curL = Math.max(l2, l3);
        curR = Math.min(r2, r3);
        if (curL <= curR) {
            maxSum = Math.max(maxSum, 2 * curR);
        }

        System.out.println(maxSum);
    }
}

import sys

def solve():
    try:
        line = sys.stdin.readline().strip()
        if not line:
            return
        
        l1, r1, l2, r2, l3, r3 = map(int, line.split())
        
        max_sum = -1
        
        # Pair 1: [l1, r1] and [l2, r2]
        cur_l = max(l1, l2)
        cur_r = min(r1, r2)
        if cur_l <= cur_r:
            max_sum = max(max_sum, 2 * cur_r)
            
        # Pair 2: [l1, r1] and [l3, r3]
        cur_l = max(l1, l3)
        cur_r = min(r1, r3)
        if cur_l <= cur_r:
            max_sum = max(max_sum, 2 * cur_r)
            
        # Pair 3: [l2, r2] and [l3, r3]
        cur_l = max(l2, l3)
        cur_r = min(r2, r3)
        if cur_l <= cur_r:
            max_sum = max(max_sum, 2 * cur_r)
            
        print(max_sum)

    except (IOError, ValueError):
        return

solve()

算法及复杂度

  • 算法：枚举

  • 时间复杂度：。

    • 该算法只涉及固定次数的比较和算术运算，与输入的区间端点值大小无关。

  • 空间复杂度：。

    • 我们只使用了有限的几个变量来存储输入和中间结果。