#include <cstdio>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
using namespace std;

int main()
{
    int s;
    cin>>s;
    int y;
    cin>>y;
    int t;
    map<int,vector<int>> mp;
    set<int> st;
    for (int i=1; i<=s; i++) {
        cin>>t;
        if (t>20) {
          mp[t].push_back(i);
          st.insert(t);
        }
    }
    vector<int> num(st.begin(),st.end());
    sort(num.rbegin(),num.rend());
    if (y>st.size()) {
        cout<<num[st.size()-1]<<' ';
        auto it=mp[num[st.size()-1]];
        sort(it.begin(),it.end());
        for (auto a:it) {
          cout<<a<<" ";
        }
    }else {
        cout<<num[y-1]<<' ';
        auto it=mp[num[y-1]];
        sort(it.begin(),it.end());
        for (auto a:it) {
          cout<<a<<" ";
        }
    }

    

}

题面描述

塔子哥使用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(); // 关闭扫描器
    }
}