刷题笔记合集🔗

判断一组不等式是否满足约束并输出最大差

问题描述

给定一组不等式，判断是否成立并输出不等式的最大差(输出浮点数的整数部分)。

要求:

1. 不等式系数为 double 类型，是一个二维数组
2. 不等式的变量为 int 类型，是一维数组
3. 不等式的目标值为 double 类型，是一维数组
4. 不等式约束为字符串数组，只能是：">", ">=", "<", "<=", "="

例如，不等式组:

a11x1+a12x2+a13x3+a14x4+a15x5<=b1;

a21x1+a22x2+a23x3+a24x4+a25x5<=b2;

a31x1+a32x2+a33x3+a34x4+a35x5<=b3;

最大差 = max{(a11x1+a12x2+a13x3+a14x4+a15x5-b1),(a21x1+a22x2+a23x3+a24x4+a25x5-b2),(a31x1+a32x2+a33x3+a34x4+a35x5-b3)}，

类型为整数(输出浮点数的整数部分)。

输入格式

a11,a12,a13,a14,a15,a21,a22,a23,a24,a25,a31,a32,a33,a34,a35,x1,x2,x3,x4,x5,b1,b2,b3,<=,<=,<=

1. 不等式组系数(double 类型):

a11,a12,a13,a14,a15

a21,a22,a23,a24,a25

a31,a32,a33,a34,a35

2. 不等式变量(int 类型):x1,x2,x3,x4,x5

3. 不等式目标值(double 类型):b1,b2,b3

4. 不等式约束(字符串类型):<=,<=,<=

输出格式

true 或者 false，最大差

样例输入

2.3,3,5.6,7,6;11,3,8.6,25,1;0.3,9,5.3,66,7.8;1,3,2,7,5;340,670,80.6;<=,<=,<=

2.36,3,6,7.1,6;1,30,8.6,2.5,21;0.3,69,5.3,6.6,7.8;1,13,2,17,5;340,67,300.6;<=,>=,<=

样例输出

false 458

false 758

数据范围

• 输入中的数值范围保证在 double 类型表示范围内
• 不等式约束只能是 ">", ">=", "<", "<=", "="
• 不等式系数、变量和目标值的数量保持一致

题解

这道题目要求判断给定的一组不等式是否满足各自的约束条件，并计算所有不等式中的最大差值。

首先来理解不等式的表达方式：

• 每个不等式形如：a1x1 + a2x2 + ... + anxn ≤ b
• 其中a是系数，x是变量，b是目标值，后面跟着约束条件（如"<="）

解题步骤：

1. 解析输入，获取系数矩阵、变量、目标值和约束条件
2. 对每个不等式，计算左侧表达式的值：sum(a[i][j] * x[j])
3. 计算每个不等式的差值：左侧表达式的值 - 目标值
4. 根据约束条件，判断每个不等式是否满足
5. 找出所有差值中的最大值
6. 输出是否全部满足约束（true/false）以及最大差值（取整数部分）

关键点在于正确地解析输入和理解约束条件的判断方法。对于约束条件，我们需要比较表达式值与目标值的关系：

• 如果约束是"<="，则表达式值应小于等于目标值
• 如果约束是">="，则表达式值应大于等于目标值
• 如果约束是"<"，则表达式值应小于目标值
• 如果约束是">"，则表达式值应大于目标值
• 如果约束是"="，则表达式值应等于目标值

时间复杂度是O(n*m)，其中n是不等式的数量，m是每个不等式中变量的数量。在本题中，n=3，m=5，所以计算量非常小。空间复杂度是O(n+m)，主要用于存储系数、变量和结果。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

def check_ineq(val, constraint):
    """检查不等式是否满足约束"""
    if constraint == ">":
        return val > 0
    elif constraint == ">=":
        return val >= 0
    elif constraint == "<":
        return val < 0
    elif constraint == "<=":
        return val <= 0
    elif constraint == "=":
        return val == 0
    return False

# 解析输入
data = input().split(';')
coeffs = []
for i in range(3):  # 读取三行系数
    coeffs.append(list(map(float, data[i].split(','))))

# 读取变量
vars = list(map(int, data[3].split(',')))

# 读取目标值
targets = list(map(float, data[4].split(',')))

# 读取约束条件
constraints = data[5].split(',')

# 计算每个不等式的差值
diffs = []
all_satisfy = True

for i in range(3):
    # 计算左侧表达式的值
    expr_val = 0
    for j in range(5):  # 5个变量
        expr_val += coeffs[i][j] * vars[j]
    
    # 计算差值
    diff = expr_val - targets[i]
    diffs.append(diff)
    
    # 检查约束是否满足
    if not check_ineq(diff, constraints[i]):
        all_satisfy = False

# 找出最大差值
max_diff = max(diffs)

# 输出结果（注意：输出浮点数的整数部分）
print(f"{str(all_satisfy).lower()} {int(max_diff)}")

• Cpp

#include