小团的 AB 队

发布于2021-04-16

上次编辑2021-04-16

问题描述

小团要组织一只队伍参加 MT 杯竞赛，某媒体赛前要对各参赛队伍实力进行评估，已知这个比赛要求每一个参赛方组织一支由 x 个人组成的 A 队，和 y 个人组成的 B 队，这个媒体在评估时会把 A 队的人员的平均实力值和 B 队人员的平均实力值相加，从而得到一个参赛方的综合实力评估。
小团可选的人手有限，只有 x+y 个人可以供他选择，但是显然不同的人员安排会有不同的综合实力评估，他希望他的综合实力评估尽可能高，请你帮助他完成分队。

格式：

输入：
- 输入第一行包含两个正整数x，y，分别表示 AB 队的人数。
- 输入第二行包含 x+y 个正整数，中间用空格隔开，第i个数字表示第i个人的实力值，每个人的实力值不会超过20000，保证任意两个人都不会有相同的实力值。
输出：
- 输出包含一个长度为 x+y 的字符串，每个字符是 'A'或 'B'，表示某人应该被分在 A 或 B 队。如果存在多种答案，则输出字典序最小的字符串。

示例：

输入：
     4 4
     5 6 4 2 3 8 1 7
输出：AAAABBBB

提示：

• 1 <= x, y <= 20000

解题思路

假设 AB 队的总实力为 \(T\)，A 队的总实力为 \(t\)，总人数为 \(N=x+y\)，则题目就是要使得下式最大。

\[ p=\frac{t}{x} + \frac{T-t}{y} = \frac{t}{x} + \frac{T-t}{N-x} = \frac{t(N-2x)+Tx}{(N-x)x} \]

\(N,x,T\) 都是常数。

• 如果 \(N-2x=0\)，则 \(p\) 为常数，故按照题目要求字典序最小，即前 \(x\) 为 A 队，后 \(y\) 个为 B 队。
• 如果 \(N-2x \gt 0\)，则 \(t\) 越大越好，即 实力最大 的前 \(x\) 个数（实力值相同时，下标小的排在前面）为 A 队，其余为 B 队。
• 如果 \(N-2x \lt 0\)，则 \(t\) 越小越好，即 实力最小 的前 \(x\) 个数（实力值相同时，下标小的排在前面）为 A 队，其余为 B 队。

Python

import sys
from typing import List

readline = sys.stdin.readline


def readint() -> int:
    return int(readline().strip())


def readstr() -> str:
    return readline().strip()


def readints() -> List[int]:
    return list(map(int, readline().strip().split()))


x, y = readints()
A = [(x, i) for i, x in enumerate(readints())]
if x == y:
    print("A" * x + "B" * y)
else:
    A.sort()
    ans = ["B"] * (x + y)
    if x > y:
        for i in range(x):
            ans[A[i][1]] = "A"
    else:
        for i in range(y, x + y):
            ans[A[i][1]] = "A"
    print("".join(ans))

C++

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    int x, y;
    cin >> x >> y;
    vector<int> A(x + y);
    for (auto &t : A) {
        cin >> t;
    }
    if (x == y) {
        cout << string(x, 'A') << string(y, 'B') << '\n';
    } else {
        vector<pair<int, int>> B(x + y);
        for (int i = 0; i < x + y; ++i) {
            B[i] = {A[i], i};
        }
        sort(B.begin(), B.end());
        string ans(x + y, 'B');
        if (x > y) {
            for (int i = 0; i < x; ++i) {
                ans[B[i].second] = 'A';
            }
        } else {
            for (int i = y; i < x + y; ++i) {
                ans[B[i].second] = 'A';
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

返回顶部

在手机上阅读