【贪心6】小塔贴标签

问题分析

小塔需要给物品贴标签，每个物品只能贴上适合的标签或不贴标签。每种标签最多只能使用一次，因此需要在合理分配标签的情况下，最大化所有物品的美观值之和。

对于每个物品来说，有两个可能的美观值：

1. 如果贴上适合的标签 a_i，则其美观值为 b_i。
2. 如果没有贴上标签，则其美观值为 c_i。

我们需要通过合理地分配标签，保证每个标签只使用一次，最大化所有物品的美观值。

思路

1. 标签分配：我们首先将物品根据它们适合的标签进行分组，记录每个标签所对应的物品索引。
2. 优先选择贴标签：对于每个标签所对应的物品，优先选择能够带来更高美观值的物品贴标签。如果物品不能贴标签，就选择不贴标签的美观值。
3. 排序策略：每个标签所对应的物品排序时，应该根据 b_i - c_i（即贴上标签和不贴标签的美观值差）来排序。这样可以优先选择那些能够通过贴标签获得更大美观值的物品。

解决方案

1. 我们首先用一个数组 idx 将每个标签对应的物品索引存储。
2. 然后，对于每个标签所对应的物品，按 b_i - c_i 的差值降序排序，以优先选择那些差值大的物品贴上标签。
3. 对于每个标签所对应的物品，最优选择是：第一个物品贴上标签，剩下的物品选择不贴标签。

代码实现

python

def max_aesthetic_value(n, m, a, b, c):
    # 创建一个大小为 m+1 的列表，用于存储每个标签对应的物品索引
    idx = [[] for _ in range(m + 1)]
    
    # 将每个物品根据它适合的标签分类存储
    for i in range(n):
        idx[a[i]].append(i)
    
    total_value = 0  # 初始化总美观值为0
    
    # 对每个标签所对应的物品进行处理
    for lst in idx:
        if not lst:
            continue  # 如果某个标签没有对应物品，跳过
        
        # 对标签对应的物品按 b[i] - c[i] 降序排序
        lst.sort(key=lambda x: c[x] - b[x])  # 先贴标签的美观值优先
        
        # 给第一个物品贴标签，选择 b[i] 或 c[i] 中更大的值
        total_value += max(b[lst[0]], c[lst[0]])  # 优先选择贴标签
        
        # 处理剩下的物品，全部选择不贴标签的美观值
        for i in lst[1:]:
            total_value += c[i]  # 剩下的物品选择不贴标签
    
    return total_value  # 返回总美观值

# 输入部分
n, m = map(int, input().split())  # 物品数量 n，标签种类 m
a = list(map(int, input().split()))  # 每个物品适合的标签
b = list(map(int, input().split()))  # 每个物品贴上适合标签后的美观值
c = list(map(int, input().split()))  # 每个物品不贴上适合标签时的美观值

# 计算最大美观值
result = max_aesthetic_value(n, m, a, b, c)

# 输出结果
print(result)

java

import java.util.*;

public class Main {

    public static long getMaxAestheticValue(int n, int m, int[] a, int[] b, int[] c) {
        List<List<Integer>> idx = new ArrayList<>();
        for (int i = 0; i <= m; i++) {
            idx.add(new ArrayList<>());
        }
        for (int i = 0; i < n; i++) {
            idx.get(a[i]).add(i);
        }

        long totalValue = 0; // 使用 long 以防止溢出

        for (List<Integer> lst : idx) {
            if (lst.isEmpty()) continue;

            // 按 (b[i] - c[i]) 降序排序
            lst.sort((x, y) -> Integer.compare((b[y] - c[y]), (b[x] - c[x])));

            // 处理第一个物品，选择 b[i] 或 c[i] 中较大值
            totalValue += Math.max(b[lst.get(0)], c[lst.get(0)]);

            // 处理剩余物品，全部选择不贴标签的美观值 c[i]
            for (int i = 1; i < lst.size(); i++) {
                totalValue += c[lst.get(i)];
            }
        }

        return totalValue;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[] a = new int[n];
        int[] b = new int[n];
        int[] c = new int[n];

        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }
        for (int i = 0; i < n; i++) {
            b[i] = scanner.nextInt();
        }
        for (int i = 0; i < n; i++) {
            c[i] = scanner.nextInt();
        }

        long result = getMaxAestheticValue(n, m, a, b, c);
        System.out.println(result);
        scanner.close();
    }
}

c++

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

using namespace std;

long long max_aesthetic_value(int n, int m, const vector<int>& a, const vector<int>& b, const vector<int>& c) {
    vector<vector<int>> idx(m + 1);
    
    for (int i = 0; i < n; ++i) {
        idx[a[i]].push_back(i);
    }

    long long total_value = 0;
    for (const auto& lst : idx) {
        if (lst.empty()) continue;

        vector<int> sorted_lst = lst;
        sort(sorted_lst.begin(), sorted_lst.end(), [&c, &b](int x, int y) {
            return c[x] - b[x] < c[y] - b[y];
        });

        total_value += max(b[sorted_lst[0]], c[sorted_lst[0]]);
        for (size_t i = 1; i < sorted_lst.size(); ++i) {
            total_value += c[sorted_lst[i]];
        }
    }

    return total_value;
}

int main() {
    int n, m;
    cin >> n >> m;

    vector<int> a(n), b(n), c(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> b[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> c[i];
    }
    long long result = max_aesthetic_value(n, m, a, b, c);
    cout << result << endl;
    return 0;
}

本题为2024年9月21日美团机考原题

美团机考的介绍点击这里

题目内容

小塔正在给自己的物品贴标签。她一共有$m$种不同的标签，每种标签只有一个。 对于第$i$个物品，如果贴上$a_i$号标签，那么它的美观值为$b_i$;如果没有贴上$a_i$号标签，则其美观值为$c_i$。 小美想知道在合理的分配下，所有物品的美观值之和最大为多少。

输入描述

第一行输入两个整数$n$和$m$($1≤n,m≤10^5$)代表小美的物品个数和标签种类。 第二行输入$n$个整数$a_1,a_2,.,a_n$($1≤a_i≤m$)代表每个物品适合的标签种类. 第三行输入$n$个整数$b_1, b_2,..,b_n$($-10≤b_i≤10^6$)代表每个物品贴上适合的标签后的美观值。 第四行输入$n$个整数$c1, c2,..,c_n$($-10^6≤c_i≤10^6$)代表每个物品未贴上适合标签时的美观值。

输出描述

在一行上输出一个整数，代表所有物品美观值之和的最大值。

样例

输入

3 3
1 2 1
5 4 3
-1 2 -100

输出

6

说明

只要把第二个物品贴上$2$号标签，第三个物品贴上$1$号标签，此时美观值之和为$-1+4+3=6$