小苯送礼物

思路

这道题说白了就是一个自定义排序问题。小苯要从 n 个粉丝里选 k 个送礼物，怎么选？按"支持力度"来排。

支持力度怎么算？点赞算 1 点，收藏算 2 点，所以一个粉丝的支持力度 = 赞数 + 2 * 收藏数。

那如果两个粉丝支持力度一样呢？题目给了两层 tiebreak：

  1. 先比收藏数，收藏多的优先
  2. 收藏也一样？编号小的优先

选出前 k 名后，按编号升序输出就行。

具体做法

  1. 读入每个粉丝的赞数和收藏数，算出支持力度，记下编号
  2. 按照"支持力度降序 → 收藏数降序 → 编号升序"的规则排序
  3. 取前 k 个粉丝的编号，排个序输出

就是个排序题，关键在写对比较函数。没什么算法上的难度，考的是细心。

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    scanf("%d%d", &n, &k);

    vector<array<int, 3>> fans(n); // {支持力度, 收藏数, 编号}
    for (int i = 0; i < n; i++) {
        int likes, col;
        scanf("%d%d", &likes, &col);
        fans[i] = {likes + 2 * col, col, i + 1};
    }

    // 支持力度降序 → 收藏数降序 → 编号升序
    sort(fans.begin(), fans.end(), [](const auto& a, const auto& b) {
        if (a[0] != b[0]) return a[0] > b[0];
        if (a[1] != b[1]) return a[1] > b[1];
        return a[2] < b[2];
    });

    vector<int> res;
    for (int i = 0; i < k; i++) {
        res.push_back(fans[i][2]);
    }
    sort(res.begin(), res.end()); // 按编号升序输出

    for (int i = 0; i < k; i++) {
        if (i) printf(" ");
        printf("%d", res[i]);
    }
    printf("\n");

    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int[][] fans = new int[n][3]; // 支持力度, 收藏数, 编号
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int likes = Integer.parseInt(st.nextToken());
            int col = Integer.parseInt(st.nextToken());
            fans[i][0] = likes + 2 * col;
            fans[i][1] = col;
            fans[i][2] = i + 1;
        }

        // 支持力度降序 → 收藏数降序 → 编号升序
        Arrays.sort(fans, (a, b) -> {
            if (a[0] != b[0]) return b[0] - a[0];
            if (a[1] != b[1]) return b[1] - a[1];
            return a[2] - b[2];
        });

        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = fans[i][2];
        }
        Arrays.sort(res); // 按编号升序输出

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < k; i++) {
            if (i > 0) sb.append(' ');
            sb.append(res[i]);
        }
        System.out.println(sb);
    }
}

import sys
input = sys.stdin.readline

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

# 支持力度降序 → 收藏数降序 → 编号升序
fans.sort(key=lambda x: (-x[0], -x[1], x[2]))

res = sorted(fans[i][2] for i in range(k))
print(' '.join(map(str, res)))

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    const [n, k] = lines[0].split(' ').map(Number);
    const fans = [];
    for (let i = 0; i < n; i++) {
        const [likes, col] = lines[i + 1].split(' ').map(Number);
        fans.push([likes + 2 * col, col, i + 1]);
    }
    // 支持力度降序 → 收藏数降序 → 编号升序
    fans.sort((a, b) => {
        if (a[0] !== b[0]) return b[0] - a[0];
        if (a[1] !== b[1]) return b[1] - a[1];
        return a[2] - b[2];
    });
    const res = [];
    for (let i = 0; i < k; i++) {
        res.push(fans[i][2]);
    }
    res.sort((a, b) => a - b);
    console.log(res.join(' '));
});

复杂度

  • 时间复杂度：，排序的开销
  • 空间复杂度：，存储粉丝信息

总结

这道题没什么弯弯绕，就是考你会不会写自定义排序的比较函数。三个排序关键字：支持力度、收藏数、编号，前两个降序第三个升序，写对了就能过。唯一要注意的是支持力度的计算公式：赞数 1 + 收藏数 2，别搞反了权重。最后输出别忘了按编号升序排一下。