题解:#4288.「2023.03五级」 拼点游戏 审核通过

zswzh 2025-09-19 22:41:26 2

本题是一个贪心题

先来讲讲思路吧

要算 S 最多能得多少巧克力,首先得把 C 和 S 的卡牌都排好序,核心思路就是让 S 用大的牌去赢 C 的小牌,越多越好。

这样每赢一次就能拿 3 颗巧克力。我们可以用两个指针,分别指着排序后 S 和 C 卡牌里最小或者最大的那个数,尽可能去凑 S 的牌点数比 C 大的情况,

然后统计 S 赢的次数。

如果把牌按降序排,然后从两端开始对比,如果 S 最大的牌比 C 最大的牌大,那这轮 S 就赢了;

要是 S 最大的牌没 C 大,那就用 S 最小的牌去和 C 最大的牌比,相当于牺牲小牌

。等统计完 S 赢的轮数后,剩下没配对的牌里,再去找点数相等的,这样能算平局次数,因为平局时两边各得 2 颗,

对 S 来说也能多拿分。最后 S 的得分就是用赢的次数乘以 3,加上平局次数乘以 2,再加上输的次数乘以 1

这就是本题的思路了


接下来是本题的AC代码

仅供参考!!!!

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int maxscore(vector<int>& A, vector<int>& B)//这里求最大分数
{
    int n = A.size();
    vector<int> a = A, b = B;
    //排序
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    int a_l = 0, a_r = n - 1;
    int b_l = 0, b_r = n - 1;
    int score = 0;
    //开始贪心
    while (b_l <= b_r) 
    {
        //赢了的两种情况
        if (b[b_r] > a[a_r]) 
        {
            score += 3;
            b_r--;
            a_r--;
        }
        else if (b[b_l] > a[a_l]) 
        {
            score += 3;
            b_l++;
            a_l++;
        }
        //否则
        else 
        {
            if (b[b_l] < a[a_r])//输了
                score += 1;
            else//没有输也没有赢,那就是平局
                score += 2;
            b_l++;
            a_r--;
        }
    }
    return score;//返回分数
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    while (true) 
    {
        int n;
        if (!(cin >> n))
            return 0;
        if (n == 0)
            break;
        vector<int> C(n), S(n);
        //输入数据
        for (int i = 0; i < n; i++) cin >> C[i];
        for (int i = 0; i < n; i++) cin >> S[i];
        int smax = maxscore(C, S);//最大
        int cmax = maxscore(S, C);
        int smin = 4 * n - cmax;//最小
        cout << smax << " " << smin << "\n";
    }
    return 0;
}

给个赞吧😭

{{ vote && vote.total.up }}