题面描述

塔子哥使用Stable Diffusion的“图生图”功能生成了一些图片，并为每张图片打了分数。他希望根据自己的经验值选择出分数排名相应的图片作为下一次绘图的参考。输入包括图片的总数、塔子哥的经验值以及每张图片的评分。输出应为符合条件的图片分数和对应的编号，所有信息以空格分隔。

思路：模拟,排序,哈希表

1.我们使用一个集合 st 来记录已经出现的有效分数，和一个向量 items 来存储这些分数以便后续排序。

2.筛选:对于每一张照片的分数 x，我们首先检查它是否大于 20 分。如果不大于 20 分，则不予考虑，直接跳过。对于大于 20 分的分数，我们检查它是否已经在集合 st 中。如果在，则将其出现的下标记录到一个映射 mp 中；如果不在，则将其加入集合和 items 向量，并在映射中初始化它的下标。

3.在处理完所有照片后，我们对 items 向量进行排序，按从大到小的顺序排列，以便我们可以找到排名第y 的分数。

题解

我们需要从塔子哥生成的图片中筛选出有效的评分，以便选择合适的图片作为下一次“图生图”绘画的参考。具体步骤如下：

1. 数据结构初始化：

   • 使用一个集合 st 来记录已经出现的有效分数，这样可以确保分数的唯一性。
   • 使用一个向量 items 来存储所有有效分数，以便后续的排序操作。
   • 建立一个映射 mp，将有效分数与它们对应的图片下标关联起来，便于查找。

2. 评分筛选：

   • 对于每张图片的评分 x，首先判断其是否大于 20。如果不满足条件，则直接跳过这张图片。
   • 如果评分大于 20，检查该分数是否已经在集合 st 中：
     • 如果在集合中，说明该分数之前已出现，直接将当前图片的下标添加到映射 mp 中。
     • 如果不在集合中，则将分数插入集合 st，同时将其加入 items 向量，并在映射 mp 中初始化该分数对应的下标。

3. 排序与选择：

   • 在处理完所有图片后，使用 sort 函数对 items 向量进行排序，按照分数从大到小的顺序排列，以便查找排名第 y 的分数。
   • 最后，输出排名第 y 的分数以及所有对应的图片下标。

代码

C++代码

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

int main() {
    int s, y; // s: 图片总数, y: 塔子哥的经验值
    cin >> s >> y;

    // 记录出现过的有效分数——用于去重
    unordered_set<int> st;
    // 记录所有有效分数——用于后续排序
    vector<int> items;
    // 建立映射：有效分数 -> 出现下标（图片编号）
    unordered_map<int, vector<int>> mp;

    for (int i = 1; i <= s; i++) {
        int x; // 当前图片的评分
        cin >> x;

        // 筛选出不大于20分的照片
        if (x <= 20)
            continue; // 如果分数不符合条件，跳过

        // 如果该分数已经出现过，记录当前图片的下标
        if (st.count(x)) {
            mp[x].push_back(i);
        } else {
            // 否则，将该分数插入集合并初始化映射
            st.insert(x);
            items.push_back(x);
            mp[x] = vector<int>{ i }; // 初始化下标为当前图片
        }
    }

    // 将所有有效分数进行排序（从大到小）
    sort(items.begin(), items.end(), greater<int>());

    // 筛选符合经验值的分数
    int ans = min((int)items.size(), y); // 确保排名不会超出有效范围
    cout << items[ans - 1] << " "; // 输出排名第y的分数

    // 输出对应的所有图片下标
    int n = mp[items[ans - 1]].size(); // 获取当前分数对应的下标数量
    for (int i = 0; i < n; i++) {
        cout << mp[items[ans - 1]][i] << ((i < n - 1) ? ' ' : '\n'); // 逐个输出下标，最后一个后换行
    }

    return 0;
}

Python

def main():
    import sys
    from collections import defaultdict

    # 读取输入
    input = sys.stdin.read
    data = input().splitlines()
    
    s = int(data[0])  # 图片总数
    y = int(data[1])  # 塔子哥的经验值
    scores = list(map(int, data[2].split()))  # 图片评分列表

    # 记录出现过的有效分数——用于去重
    st = set()
    # 记录所有有效分数——用于后续排序
    items = []
    # 建立映射：有效分数 -> 出现下标（图片编号）
    mp = defaultdict(list)

    for i in range(s):
        x = scores[i]  # 当前图片的评分

        # 筛选出不大于20分的照片
        if x <= 20:
            continue  # 如果分数不符合条件，跳过

        # 如果该分数已经出现过，记录当前图片的下标
        if x in st:
            mp[x].append(i + 1)  # 图片编号从1开始
        else:
            # 否则，将该分数插入集合并初始化映射
            st.add(x)
            items.append(x)
            mp[x].append(i + 1)  # 初始化下标为当前图片编号

    # 将所有有效分数进行排序（从大到小）
    items.sort(reverse=True)

    # 筛选符合经验值的分数
    ans = min(len(items), y)  # 确保排名不会超出有效范围
    print(items[ans - 1], end=" ")  # 输出排名第y的分数

    # 输出对应的所有图片下标
    indices = mp[items[ans - 1]]  # 获取当前分数对应的下标列表
    print(" ".join(map(str, indices)))  # 逐个输出下标

if __name__ == "__main__":
    main()

java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int s = scanner.nextInt(); // 图片总数
        int y = scanner.nextInt(); // 塔子哥的经验值

        // 记录出现过的有效分数——用于去重
        Set<Integer> st = new HashSet<>();
        // 记录所有有效分数——用于后续排序
        List<Integer> items = new ArrayList<>();
        // 建立映射：有效分数 -> 出现下标（图片编号）
        Map<Integer, List<Integer>> mp = new HashMap<>();

        for (int i = 1; i <= s; i++) {
            int x = scanner.nextInt(); // 当前图片的评分

            // 筛选出不大于20分的照片
            if (x <= 20) {
                continue; // 如果分数不符合条件，跳过
            }

            // 如果该分数已经出现过，记录当前图片的下标
            if (st.contains(x)) {
                mp.get(x).add(i);
            } else {
                // 否则，将该分数插入集合并初始化映射
                st.add(x);
                items.add(x);
                mp.put(x, new ArrayList<>(Arrays.asList(i))); // 初始化下标为当前图片
            }
        }

        // 将所有有效分数进行排序（从大到小）
        Collections.sort(items, Collections.reverseOrder());

        // 筛选符合经验值的分数
        int ans = Math.min(items.size(), y); // 确保排名不会超出有效范围
        System.out.print(items.get(ans - 1) + " "); // 输出排名第y的分数

        // 输出对应的所有图片下标
        List<Integer> indices = mp.get(items.get(ans - 1)); // 获取当前分数对应的下标列表
        for (int i = 0; i < indices.size(); i++) {
            System.out.print(indices.get(i) + (i < indices.size() - 1 ? " " : "\n")); // 逐个输出下标，最后一个后换行
        }

        scanner.close(); // 关闭扫描器
    }
}

题目内容

小美是一个不那么严谨的经验主义者，他在使用Stable Diffusion“图生图”功能来画好康的图片时总想要选出上一轮最好看的那几张图片作为下一次“图生图”绘画的参考。

更一般的，“图生图”功能绘画的结果是若干张好康的图片，按照生成的先后顺序由1开始向后编号；同时，小美在心里给它们打了一个分数（不同图片分数可能相同），由于AI绘图实在是不稳定，小美决定删掉分数不大于20分的图片；随后小美会根据他阅图无数的经验得到一个经验值，然后选择图片分数排名等于该经验值的图片作为下一次“图生图”绘画的参考。（注意，这里排名采用dense_rank的方式，即分数从大到小排序，相同分数排名相同）。如果不存在排名恰好经验值的，按最大的排名。

小美希望你帮他找出可以作为“图生图”绘画参考的图片，以便于设置绘图的其他参数。

解答要求

时间限制: C/C++ 1000ms，其他语言: 2000ms 内存限制:C/C++256MB，其他语言:512MB

输入

第一行输入为“图生图”绘制的结果中图片的张数$S$

第二行输入为小美自认为的经验值$Y$:

第三行输入为小美给所有图片的评分，评分值以空格分隔。

• 1$\leq Y \leq 未被删除的图片数量 \leq 图片总数 \leq 10^4$:
• $0\leq 评分分值 \leq 100$

输出

排序最靠后的那些图片的分数和编号以空格分隔。

样例

输入

1
5 
98

输出

98 1

解释

小美的经验值$Y=5$，所有图片按照评分编号为$1$的图片被保留，分数为$98$。因此排序最靠后的那张图片的评分为排位第$1$、编号为1的入围作品，但是很显然这就是排序最靠后那张图片，那么输出 $98$ $1$

样例2

输入

14
1
11 45 14 19 19 81 0 11 45 14 19 19 81 0

输出

81 6 13

解释

被保留的图片编号分别为$2$，$6$，$9$，$13$。按分数排序后为:

81(6) 81(13) 45(2) 45(9)

他们的排名为:

1 1 2 2

y = 1 ，则取rank = 1的输出，81 6 13

样例3

输入

14
2
11 45 14 19 19 81 0 11 45 14 19 19 81 0

输出

45 2 9