【PAT乙级】微博转发抽奖

正文索引 [隐藏]

题目描述:

小明 PAT 考了满分,高兴之余决定发起微博转发抽奖活动,从转发的网友中按顺序每隔 N 个人就发出一个红包。请你编写程序帮助他确定中奖名单。

输入描述:

输入第一行给出三个正整数 M(≤ 1000)、N 和 S,分别是转发的总量、小明决定的中奖间隔、以及第一位中奖者的序号(编号从 1 开始)。随后 M 行,顺序给出转发微博的网友的昵称(不超过 20 个字符、不包含空格回车的非空字符串)。

注意:可能有人转发多次,但不能中奖多次。所以如果处于当前中奖位置的网友已经中过奖,则跳过他顺次取下一位。

输出描述:

按照输入的顺序输出中奖名单,每个昵称占一行。如果没有人中奖,则输出 Keep going...

输入样例 1:

9 3 2
Imgonnawin!
PickMe
PickMeMeMeee
LookHere
Imgonnawin!
TryAgainAgain
TryAgainAgain
Imgonnawin!
TryAgainAgain

输出样例 1:

PickMe
Imgonnawin!
TryAgainAgain

输入样例 2:

2 3 5
Imgonnawin!
PickMe

输出样例 2:

Keep going…

解题思路:

建立一个字符串队列queue用来存入中奖者的昵称,建立一个中奖者名单map,这个操作看上去是重复的,写到后面才会发现这俩者的用处。立一个flag用来记录是否有人中奖,true为没人中奖。用for循环遍历,如果这是中奖者,先判断他在不在map里,若不在map里,就把它放入map同时入队,若在map里,就跳过他顺次取下一位(S++;continue)。每次抽完中奖者之后,中将序号需要加上一个中奖间隔。最后把队列从队首开始根据“先进先出”的规则进行输出。如果flag依然为真,说明没有人中奖,输出”Keep going…”。

AC代码:

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int M,N,S;  //M为转发的总量,N为小明决定的中奖间隔,S是第一位中奖者的序号
    cin >> M >> N >> S;
    queue<string> q;  //字符串型队列
    map<string, int> m;
    bool flag = true;    //flag用来记录是否有人中奖,true为没人中奖
    for (int i = 1; i <= M; i++)
    {
        string temp;
        cin >> temp;
        if(i==S)   //中奖者
        {
            flag = false;
            if(m[temp]==0)
            {
                m[temp]++;
                q.push(temp);
            }
            else
            {
                S++;
                continue;
            }
            S += N;
        }
    }
    while(!q.empty())   //清仓大甩卖
    {
        cout << q.front() << endl;
        q.pop();
    }
    if(flag)
    {
        cout << "Keep going..." << endl;
    }
    return 0;
}