P1786. 帮贡排序

发表于 分类于 阅读次数： Waline： 本文字数： 751 阅读时长 ≈ 3 分钟

考点

  • 哈希函数
  • 模拟

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <bits/stdc++.h>

using namespace std;

string offer[7] = {"BangZhu", "FuBangZhu", "HuFa", "ZhangLao", "TangZhu", "JingYing", "BangZhong"};

int offer_cnts[7] = {1, 2, 2, 4, 7, 25, 500};

int N;

//题目提到“原来靠前的现在也要靠前”，所以还需要idx_记录相对位置
struct Member
{
    string name_, offer_;
    int contri_, rank_, idx_;
} mem[550];

//精髓就在这里，字符串的优先级映射为数字，即可排序啦！
int hsh(string s)
{
    if (s == "BangZhu")
        return 6;
    else if (s == "FuBangZhu")
        return 5;
    else if (s == "HuFa")
        return 4;
    else if (s == "ZhangLao")
        return 3;
    else if (s == "TangZhu")
        return 2;
    else if (s == "JingYing")
        return 1;
    return 0;
}

bool cmp1(Member a, Member b)
{
    if (a.contri_ != b.contri_)
        return a.contri_ > b.contri_;
    //非常恶心的坑点！帮贡相同则按原来顺序
    return a.idx_ < b.idx_;
}

bool cmp2(Member a, Member b)
{
    if (a.offer_ != b.offer_)
        return hsh(a.offer_) > hsh(b.offer_);
    else if (a.rank_ != b.rank_)
        return a.rank_ > b.rank_;
    return a.idx_ < b.idx_;
}

void print()
{
    for (int i = 0; i < N; ++i)
    {
        cout << mem[i].name_ << " " << mem[i].offer_ << " " << mem[i].rank_ << endl;
    }
}

int main()
{
    cin >> N;
    for (int i = 0; i < N; ++i)
    {
        cin >> mem[i].name_ >> mem[i].offer_ >> mem[i].contri_ >> mem[i].rank_;
        mem[i].idx_ = i;
    }
    // 因为题目给的数据已经是按职位和等级排序了
    // 所以帮主和副帮主的位置不能动！哪怕帮贡有差别
    sort(mem + 3, mem + N, cmp1);
    int i = 3, idx = 2;
    while (i < N)
    {
        while (offer_cnts[idx] && i < N)
        {
            mem[i++].offer_ = offer[idx];
            --offer_cnts[idx];
        }
        ++idx;
    }
    sort(mem + 3, mem + N, cmp2);
    print();
    return 0;
}

思路

这道题是授权题，但是质量真的不好....因为立意实在过于模糊

第一个难点

题目说输出结果中，职位第一关键字，等级第二关键字

第一反应肯定是一次排序：先按帮贡优先，再按等级优先，然后修改他们的职位即可

然而，最终结果有很多相同的职位！比如有数据A{帮贡100, 等级4},B{帮贡50，等级8}，且最终A与B职位一样

按照上述排序的优先级，结果是先A后B；但实际上应该先B后A，因为A与B最终职位一样，但B的等级大于A

所以需要两次排序！！！！！

第二次排序先根据职位排序，再根据等级排序，最后按照输入顺序排序

第二个难点

刚才提到按职位排序，可职位是字符串，怎么排序呢？

编写一个哈希函数，将其转化为数字就可以

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//精髓就在这里，字符串的优先级映射为数字，即可排序啦！
int hsh(string s)
{
    if (s == "BangZhu")
        return 6;
    else if (s == "FuBangZhu")
        return 5;
    else if (s == "HuFa")
        return 4;
    else if (s == "ZhangLao")
        return 3;
    else if (s == "TangZhu")
        return 2;
    else if (s == "JingYing")
        return 1;
    return 0;
}

第一个坑点

因为题目说了帮主和副帮主不能动，所以排序的时候要避开这三个人

第二个坑点

第一次排序的代码中，还需要再加一条输入顺序的优先才能AC...百思不得其解

1
2
3
4
5
6
7
bool cmp1(Member a, Member b)
{
    if (a.contri_ != b.contri_)
        return a.contri_ > b.contri_;
    //非常恶心的坑点！帮贡相同则按原来顺序
    return a.idx_ < b.idx_;
}