NOTES · 学习笔记

第十七届蓝桥杯省赛 B 组:整数对计数与队伍分组

LeetCode数学 · 中等约 8 分钟

题目

整数对计数

我们看这道题,简化一下题目就变成了:给定一个 N = 2026202520242023。

x + y = N,x < y;我们要求满足这几个条件的 <x, y> 有几个。

这道题我们可以直接根据数学逻辑去解决。

我们来举几个例子:

假设 N = 5(奇数),x = 0、1、2,满足条件的一共有 3 组。

假设 N = 6(偶数),x = 0、1、2,满足条件的一共有 3 组。

所以我们能推出公式:(N + 1) / 2。

我们来观察一下,满足条件的 x 是从 0 开始的。因为要求 x < y,又有 x + y = N,所以 y = N - x。

代入条件 x < y,得到 x < N - x,整理后得到 2x < N。

也就是说,x 最大只能取到小于 N / 2 的整数,因此 x 的取值范围是 0 ≤ x < N / 2。

因为 x 从 0 开始,所以满足条件的组合数量为 (N + 1) / 2。

#include <iostream>
using namespace std;
int main()
{
    long long N = 2026202520242023;
    long long count = (N + 1) / 2;
    cout << count;
    return 0;
}

队伍分组

我们看这道题,提取一下有效信息,N 表示有 N 种不同的位置,例如 N = 5 表示有 5 种不同位置,N = 6 表示有六种不同位置。

还包括一个数组 vector,这个数组中的数字加起来就是总人数。看题,我们要判断是否能将所有人员分配到不同的位置进行比赛,且不能落下任何一人。

所以要满足的条件就是:1,总人数 % 5 == 0,因为 5 人一组。2,Ai <= k,每个位置的人数为 Ai。假设 Ai 为 2,就表示玩这个位置的人有两个人,那么 Ai = 2。如果某个位置需要 2 个人,那么至少需要 2 支队伍才能满足这个位置的人员需求。如果总共有 3 支队伍,那么这个位置最多只能有 3 个人,否则就会有队伍缺少该位置的参赛人员。

我们先来看第一个条件:

总人数必须能够被 5 整除,因为每支队伍需要 5 个人。如果总人数不能被 5 整除,那么就无法将所有人分成完整的队伍,必然会有人无法参加比赛。

接下来是第二个条件。

假设总人数为 sum,那么能够分成的队伍数量就是:int k = sum / 5。

每个位置需要的人数为 A[i]。因为每支队伍都需要有一个人参加每个位置的比赛,所以如果某个位置需要的人数超过了队伍数量,那么就会出现队伍没有人参加这个位置的情况。因此,必须满足 A[i] <= k。

当这两个条件都满足时,就可以将所有人员分配到不同的位置进行比赛,不会落下任何一人。

所以我们可以得出结论:如果 sum % 5 != 0,那么不能完成分组;如果存在 A[i] > k,那么也不能完成分组;只有两个条件都满足,才能完成分组。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int T;
    int N;
    scanf("%d", &T);
    while (T > 0) {
        scanf("%d", &N);
        vector<int> A(N);
        for (int i = 0; i < N; i++) {
            scanf("%d", &A[i]);
        }
        T--;
        int sum = 0;
        for (int i = 0; i < N; i++) {
            sum += A[i];
        }
        if (sum % 5 != 0) {
            cout << "F" << endl;
        } else {
            int k = sum / 5;
            bool ok = true;
            for (int i = 0; i < N; i++) {
                if (A[i] > k) {
                    ok = false;
                    break;
                }
            }
            if (ok == true) {
                cout << "T" << endl;
            } else {
                cout << "F" << endl;
            }
        }
    }
    return 0;
}