【PAT甲级 - C++题解】1124 Raffle for Weibo Followers

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

Sample Output 1:

PickMe
Imgonnawin!
TryAgainAgain

Sample Input 2:

2 3 5
Imgonnawin!
PickMe
• 1
• 2
• 3

Sample Output 2:

Keep going...

思路

先将所有信息用 name 来保存，方便查找。并且可以用哈希表来存储中奖者的信息，排除重复中奖的情况。

从第一位中奖者位置 s 开始查找，但是要注意当前查找位置 k 不能超过总信息数 m 。

如果当前中奖者之前已经中过奖，需要往后延一位。反之，输出该中奖者信息，然后将其信息放入哈希表中，并寻找下一位中奖者。

如果哈希表为空，则说明没有中奖者，输出 Keep going... 。

代码

#include<bits/stdc++.h>
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;
}