【PAT甲级】1124 Raffle for Weibo Followers

✍个人博客：https://blog.csdn.net/Newin2020?spm=1011.2415.3001.5343
📚专栏地址：PAT题解集合
📝原题地址：题目详情 - 1124 Raffle for Weibo Followers (pintia.cn)
🔑中文翻译：微博转发抽奖
📣专栏定位：为想考甲级PAT的小伙伴整理常考算法题解，祝大家都能取得满分！
❤️如果有收获的话，欢迎点赞👍收藏📁，您的支持就是我创作的最大动力💪

1124 Raffle for Weibo Followers

John got a full mark on PAT. He was so happy that he decided to hold a raffle（抽奖） for his followers on Weibo – that is, he would select winners from every N followers who forwarded his post, and give away gifts. Now you are supposed to help him generate the list of winners.

Input Specification:

Each input file contains one test case. For each case, the first line gives three positive integers M (≤ 1000), N and S, being the total number of forwards, the skip number of winners, and the index of the first winner (the indices start from 1). Then M lines follow, each gives the nickname (a nonempty string of no more than 20 characters, with no white space or return) of a follower who has forwarded John’s post.

Note: it is possible that someone would forward more than once, but no one can win more than once. Hence if the current candidate of a winner has won before, we must skip him/her and consider the next one.

Output Specification:

For each case, print the list of winners in the same order as in the input, each nickname occupies a line. If there is no winner yet, print Keep going... instead.

Sample Input 1:

9 3 2
Imgonnawin!
PickMe
PickMeMeMeee
LookHere
Imgonnawin!
TryAgainAgain
TryAgainAgain
Imgonnawin!
TryAgainAgain
1
2
3
4
5
6
7
8
9
10

Sample Output 1:

PickMe
Imgonnawin!
TryAgainAgain
1
2
3

Sample Input 2:

2 3 5
Imgonnawin!
PickMe
1
2
3

Sample Output 2:

Keep going...
1

思路

1. 先将所有信息用 name 来保存，方便查找。并且可以用哈希表来存储中奖者的信息，排除重复中奖的情况。
2. 从第一位中奖者位置 s 开始查找，但是要注意当前查找位置 k 不能超过总信息数 m 。
3. 如果当前中奖者之前已经中过奖，需要往后延一位。反之，输出该中奖者信息，然后将其信息放入哈希表中，并寻找下一位中奖者。
4. 如果哈希表为空，则说明没有中奖者，输出 Keep going... 。

代码

#include
using namespace std;

const int N = 1010;
string name[N];
int m, n, s;

int main()
{
    cin >> m >> n >> s;
    for (int i = 1; i <= m; i++)   cin >> name[i];

    unordered_set<string> hash; //用于判断重复中奖者
    int k = s;    //从第s个位置开始
    while (k <= m)
    {
        if (hash.count(name[k])) k++;    //如果该人中过奖，则往后延
        else
        {
            cout << name[k] << endl;
            hash.insert(name[k]);   //加入哈希表中
            k += n;   //找下一个中奖者
        }
    }

    //如果hash表为空，说明没有中奖者
    if (hash.empty())    puts("Keep going...");

    return 0;
}
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