题解 | #小苯送礼物#

题目链接

BGN22 小苯送礼物

题目描述

小苯是“小红书app”的一名博主，他有 $N$ 名粉丝，编号从 1 到 $N$ 。他想选择其中对他支持力度最大的前 $K$ 名粉丝送礼物。

支持力度计算：

每点一次赞，增加 1 点支持力度。
每收藏一篇文章，增加 2 点支持力度。

筛选规则（按优先级）：

总支持力度：越高越好。
收藏数：如果支持力度相同，收藏数越多越好。
粉丝编号：如果前两者都相同，编号越小越好。

请你帮小苯找出他应该送礼物的 $K$ 名粉丝的编号。

输入描述

第一行两个正整数 $N, K$ 。接下来 $N$ 行，每行两个整数 $likes, collections$ ，分别表示第 $i+1$ 位粉丝的点赞数和收藏数。

输出描述

输出一行 $K$ 个正整数，表示小苯选择的粉丝们的编号，并按升序输出。

样例

输入

输出

1 4

解题思路

本题的核心是根据一个三层优先级的规则对粉丝进行排序，并选出前 $K$ 名。

1. 数据结构 为了方便排序，我们需要将每个粉丝的多个属性（编号、点赞数、收藏数、总支持度）关联起来。使用一个结构体或类来封装每个粉丝的信息是最佳选择。

id: 粉丝的原始编号。
likes: 点赞数。
collections: 收藏数。
support: 总支持度，可以根据 $likes$ 和 $collections$ 计算得出， $support = likes \cdot 1 + collections \cdot 2$ 。

2. 自定义排序 排序的规则有三个层次，优先级从高到低：

support 降序。
collections 降序。
id 升序。

我们可以实现一个自定义的比较函数或逻辑，并将其应用于标准库的排序函数中。

3. 最终输出 题目要求最终输出的粉丝编号是升序的。在选出前 $K$ 名粉丝后，需要对他们的编号进行一次独立的升序排序。

算法步骤：

读入粉丝数 $N$ 和礼物数 $K$ 。
创建一个结构体/类数组，用于存储 $N$ 名粉丝的信息。
循环 $N$ 次，读入每位粉丝的 $likes$ 和 $collections$ ，计算 $support$ ，并将完整的粉丝信息（包括 id = i + 1）存入数组。
使用自定义比较逻辑对粉丝数组进行排序。
选取排序后的前 $K$ 个粉丝。
提取这 $K$ 个粉丝的 id，存入一个新的列表。
对这个 id 列表进行升序排序。
按格式要求输出 id 列表。

代码

c++
java
python

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

using namespace std;

struct Fan {
    int id;
    int likes;
    int collections;
    int support;
};

bool compareFans(const Fan& a, const Fan& b) {
    if (a.support != b.support) {
        return a.support > b.support;
    }
    if (a.collections != b.collections) {
        return a.collections > b.collections;
    }
    return a.id < b.id;
}

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

    vector<Fan> fans(n);
    for (int i = 0; i < n; ++i) {
        fans[i].id = i + 1;
        cin >> fans[i].likes >> fans[i].collections;
        fans[i].support = fans[i].likes + fans[i].collections * 2;
    }

    sort(fans.begin(), fans.end(), compareFans);

    vector<int> winner_ids;
    for (int i = 0; i < k; ++i) {
        winner_ids.push_back(fans[i].id);
    }

    sort(winner_ids.begin(), winner_ids.end());

    for (int i = 0; i < k; ++i) {
        cout << winner_ids[i] << (i == k - 1 ? "" : " ");
    }
    cout << '\n';

    return 0;
}

import java.util.Scanner;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;

class Fan {
    int id;
    int likes;
    int collections;
    int support;

    public Fan(int id, int likes, int collections) {
        this.id = id;
        this.likes = likes;
        this.collections = collections;
        this.support = likes + collections * 2;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();

        Fan[] fans = new Fan[n];
        for (int i = 0; i < n; i++) {
            fans[i] = new Fan(i + 1, sc.nextInt(), sc.nextInt());
        }

        Arrays.sort(fans, new Comparator<Fan>() {
            @Override
            public int compare(Fan a, Fan b) {
                if (a.support != b.support) {
                    return b.support - a.support;
                }
                if (a.collections != b.collections) {
                    return b.collections - a.collections;
                }
                return a.id - b.id;
            }
        });

        List<Integer> winner_ids = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            winner_ids.add(fans[i].id);
        }
        
        Collections.sort(winner_ids);

        for (int i = 0; i < k; i++) {
            System.out.print(winner_ids.get(i) + (i == k - 1 ? "" : " "));
        }
        System.out.println();
    }
}

# -*- coding: utf-8 -*-

n, k = map(int, input().split())
fans = []
for i in range(n):
    likes, collections = map(int, input().split())
    support = likes + 2 * collections
    # 存储 [support, collections, id]
    fans.append([support, collections, i + 1])

# 排序：support降序, collections降序, id升序
fans.sort(key=lambda x: (-x[0], -x[1], x[2]))

# 选取前k个粉丝的id
winner_ids = []
for i in range(k):
    winner_ids.append(fans[i][2])

# 对id升序排序并输出
winner_ids.sort()
print(*winner_ids)

算法及复杂度

算法：自定义排序
时间复杂度： $O(N \cdot \log N)$ ，其中 $N$ 是粉丝数量。主要开销来自于对所有粉丝信息进行排序。后续对 $K$ 个id的排序时间复杂度为 $O(K \cdot \log K)$ ，被前者覆盖。
空间复杂度： $O(N)$ ，用于存储 $N$ 名粉丝的信息。