小苯送礼物

[题目链接](https://www.nowcoder.com/practice/466e02d2177845589ab5fa5decc2857f)

思路

本题是一道排序模拟题。给定 名粉丝的点赞数和收藏数，需要选出支持力度最大的前 名粉丝。

计算支持力度

每名粉丝的支持力度 。

排序规则

题目给出了三级排序标准：

  1. 支持力度越大越优先；
  2. 支持力度相同时，收藏数越多越优先；
  3. 以上都相同时，编号越小越优先（关注时间更早）。

实现步骤

  1. 读入每名粉丝的点赞数 和收藏数 ，计算其支持力度 ，并记录编号；
  2. 按上述三级规则对所有粉丝进行排序；
  3. 取排序后前 名粉丝的编号，再按编号升序输出。

样例演示

4 名粉丝的支持力度分别为：

粉丝编号 点赞 收藏 支持力度
1 1 2
2 2 1
3 3 0
4 1 3

选前 名：粉丝 4（力度 7）和粉丝 1（力度 5）。按编号升序输出：1 4。

代码

#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 x, y;
        scanf("%d%d", &x, &y);
        fans[i] = {x + 2 * y, y, 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 Exception {
        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 x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            fans[i][0] = x + 2 * y;
            fans[i][1] = y;
            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);
    }
}

复杂度分析

  • 时间复杂度：，排序为主要开销。
  • 空间复杂度：，存储所有粉丝的信息。