NSOqwq

题解 P7259 【[COCI2009-2010#3] SORT】

P7259首A,发个题解纪念一下。

题目大意

给你个数列,要你按数的出现次数排列。出现次数最多的排在前面。

当两个数出现次数一样多时,这两个数中第一次出现得最早的,排在前面。

做法

开两个 map,一个记录数出现的次数,一个记录数第一次出现时的下标。

然后边输入边处理 map,输入完了以后 sort 一下然后输出即可。

map 就是功能类似字典的一个数据结构,这个不知道的话可以使用搜索引擎搜索。

代码

#include <cstdio>
#include <map>
#include <algorithm>
int n, c, a[1001];
std::map<int, int> m; // 记录出现次数
std::map<int, int> m2; // 记录第一次出现的下标
bool compare(int a, int b) {
    if (m[a] == m[b]) { // 如果出现次数相同
        return m2[a] < m2[b]; // 按第一次出现的下标排序
    }
    return m[a] > m[b]; // 按出现次数排序
}

// 先看主程序
int main() {
    scanf("%d%d", &n, &c); // 注意c在这个程序里虽然没有用到,但还是得输入一下
    for (int i = 1; i <= n; i += 1) {
        scanf("%d", &a[i]);
        if (m.find(a[i]) == m.end()) { // 这个数第一次出现
            m2[a[i]] = i; // 记录下标
            m[a[i]] = 1;
        } else {
            m[a[i]] += 1; // 出现次数加一
        }
    }
    std::sort(a + 1, a + n + 1, compare); // 排序
    for (int i = 1; i <= n; i += 1) {
        printf("%d ", a[i]); // 输出
    }
    return 0;
}

2021-01-09 10:24:54 in 题解