算法实战：牛客14777题足球积分分配问题的数学建模与枚举解法

7个月前 (08-22)牛客题解209

一、问题背景与理解

牛客14777题要求判断在给定的比赛场次(n)、已比赛场次(k)和两队分差(d1,d2)条件下，是否存在合理的积分分配方案。这是一个典型的数学建模与枚举验证问题。

二、完整代码实现（带详细注释）

#include <iostream>
#include <cmath>
using namespace std;

bool check(long long n, long long k, long long d1, long long d2) {
    // 特殊情况处理：比赛已结束
    if (k == 0) return (n % 3 == 0);  // 未开始比赛需能均分
    if (n == k) return (d1 == 0 && d2 == 0);  // 比赛结束应无分差
    
    long long total = n * 3;  // 总积分
    long long remaining = n - k;  // 剩余比赛场次
    
    // 枚举4种可能的比分组合
    for (int s1 : {-1, 1}) {  // 第一组分差方向
        for (int s2 : {-1, 1}) {  // 第二组分差方向
            long long sum = 2 * s1 * d1 + s2 * d2;
            if ((k - sum) % 3 != 0) continue;  // 积分需能被3整除
            
            long long a = (k - sum) / 3;  // 队A积分
            long long b = a + s1 * d1;    // 队B积分
            long long c = b + s2 * d2;    // 队C积分
            
            // 检查非负性
            if (a < 0 || b < 0 || c < 0) continue;
            
            // 计算需要调整的分数
            long long max_score = max(a, max(b, c));
            long long needed = (max_score - a) + (max_score - b) + (max_score - c);
            
            // 检查剩余比赛是否足够
            if (needed <= remaining && (remaining - needed) % 3 == 0) {
                return true;
            }
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);  // 加速输入输出
    cin.tie(nullptr);
    
    int t;  // 测试用例数
    cin >> t;
    while (t--) {
        long long n, k, d1, d2;
        cin >> n >> k >> d1 >> d2;
        cout << (check(n, k, d1, d2) ? "yes" : "no") << endl;
    }
    return 0;
}