首页 > 试题广场 >

小苯送礼物

[编程题]小苯送礼物
  • 热度指数：6403 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小苯是“小红书app”的一名博主，这天他想要给自己的“铁粉”送一些礼物。

他有 n 名粉丝，编号从 1 到 n，但他只能选择其中 k 名送礼物，他决定选择其中对他支持力度最大的前 k 名粉丝。
（如果两名支持力度相同，则优先选择收藏数更多的，如果都一样，则优先选择编号更小的（因为这意味着他关注小苯的时间更早））

具体的：每名粉丝如果每给小苯点一次赞，则他对小苯就增加了 1 点支持力度，如果他每收藏小苯的一篇文章，则他对小苯增加 2 点支持力度。

现在小苯想知道，他应该选择哪 k 名粉丝送出礼物，请你帮帮他吧。

输入描述:
输入包含 n+1行。
第一行两个正整数 n, k\ (1 \leq k \leq n \leq 10^5)，分别表示对小苯有过支持的粉丝个数，以及小苯选择送礼的粉丝个数。
接下来 n 行，每行两个整数 x_i, y_i\ (0 \leq x_i, y_i \leq 10^5)，表示第 i 位粉丝给小苯点过 x 次赞，收藏过 y 个小苯的文章。


输出描述:
输出包含一行 k 个正整数，表示小苯选择出送礼物的粉丝们的编号。（按照升序输出）
示例1

输入

4 2
1 2
2 1
3 0
1 3

输出

1 4
算法知识视频讲解
查看答案及解析
添加回答
Python3
Sinking_sub头像 Sinking_sub
n, k = map(int, input().split());fans = []

for i in range(n):
    x, y = map(int, input().split())
    fans.append((x + 2 * y,y,i+1))
fans.sort(key=lambda t: (-t[0], -t[1], t[2]));mm=[];cc=[]  
for i in range(k):
    mm.append(fans[i])
for i in range(k):
    cc.append(mm[i][2])

print(' '.join(str(x) for x in sorted(cc)))
发表于 2026-01-09 18:01:13 回复(0)
Python3
牛客559248288号头像 牛客559248288号
import heapq

def main():
    import sys
    input = sys.stdin.read().split()  # 快速读取输入（适配大数据）
    ptr = 0
    n, k = int(input[ptr]), int(input[ptr+1])
    ptr += 2
   
    # 构造堆：存储 (-支持力度, -收藏数, 编号)，利用小顶堆找前k大
    heap = []
    for idx in range(1, n+1):
        x = int(input[ptr])
        y = int(input[ptr+1])
        ptr += 2
        support = x + 2 * y  # 计算支持力度
        # 堆元素：(-支持力度, -收藏数, 编号)，小顶堆会优先弹出“更小”的元组（即更差的粉丝）
        if len(heap) < k:
            heapq.heappush(heap, ( support, idx ))
        else:
            # 仅当当前粉丝比堆顶更优时，替换堆顶
            if support > heap[0][0]:
                heapq.heappop(heap)
                heapq.heappush(heap, ( support, idx ))
   
    # 提取堆中所有粉丝编号，并按升序排序
    selected = [item[1] for item in heap]
    selected.sort()
   
    # 输出结果（按升序）
    print(' '.join(map(str, selected)))

if __name__ == "__main__":
    main()
发表于 2025-12-23 23:16:17 回复(0)
Python3
忧伤的双曲线头像 忧伤的双曲线
n,k = map(int,input().split())

dic = {}
for i in range(1,n+1):
    x,y = map(int,input().split())
    dic[i] = [x+2*y,y]
sorted_keys = sorted(dic.keys(),key=lambda x:(-dic[x][0],-dic[x][1],x))
answer = sorted(sorted_keys[0:k])

print(' '.join(map(str,answer)))
发表于 2025-08-25 23:23:49 回复(0)
提交观点

问题信息

数组 模拟 小红书 排序
难度：
3条回答 1355浏览

热门推荐

相关试题

小苯送礼物

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号