题解：P11960 [GESP202503 五级] 平均分配

Minnieの藍蝶 · 2025-03-24 13:02:29 · 题解

思路

从题目描述中可以看出这是一道贪心的题目。

贪心思想：既然想要收入最大，就要选取单个物品中出价尽量高，且与出价较低者的出价差距尽可能大。

解题方法

计算出第 i 件物品小 A 与小 B 出价的差。对这 i 件物品两者的差价进行降序排序，选取尽可能大的价格作为售价。

AC code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2 * 1e5 + 10;
int n, ans, C, B;
struct stu
{
    int c, b, res;
}a[N];
bool cmp (stu x, stu y)
{
    return x.res > y.res;
}
signed main ()
{
    cin >> n;
    for (int i = 1; i <= n * 2; i ++) scanf ("%lld", &a[i].b);
    for (int i = 1; i <= n * 2; i ++) scanf ("%lld", &a[i].c);
    for (int i = 1; i <= n * 2; i ++)
        a[i].res = abs (a[i].c - a[i].b);   // 记录差
    sort (a + 1, a + n * 2 + 1, cmp);   // 降序排序
    for (int i = 1; i <= n * 2; i ++)
    {
        if (a[i].b > a[i].c)    //  小B更优 
        {
            if (B < n)
            {
                B ++;
                ans += a[i].b;
            }
            else
            {
                C ++;
                ans += a[i].c;
            }
        }
        else if (a[i].c > a[i].b)   //  小C更优 
        {
            if (C < n)
            {
                C ++;
                ans += a[i].c;
            }
            else
            {
                B ++;
                ans += a[i].b;
            }
        }
        else    //  出价相同 
        {
            if (C < n)
            {
                C ++;
                ans += a[i].c;
            }
            else
            {
                B ++;
                ans += a[i].b;
            }
        }
    }
    printf ("%lld", ans);
    return 0;
}