PAT A1124 Raffle for Weibo Followers (20分) [map vector]

题目

John got a full mark on PAT. He was so happy that he decided to hold a rafle（抽奖） for his followers on Weibo — that is, he would select winners from every N followers who forwarded his post, and give away gifs. 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
Sample Output 2:
Keep going…

题目分析

从转发自己微博的粉丝中，抽取幸运者送奖品，已知转发微博的粉丝列表（有重复昵称，因为一位粉丝可以多次转发），每间隔n位粉丝获得奖品
1 每个人可以多次转发微博
2 每个人只能获得一次奖励，若已获奖的粉丝再次被抽取到，跳过，到下个粉丝

解题思路

因为获奖者需要按照输入的顺序打印且每个人只能获得一次奖品，所以使用map存储获奖记录
若map[获奖者]==1，说明已经获得过奖品，跳过，到下一个粉丝

Code

Code 01

#include <iostream>
#include <vector>
#include <map>
using namespace std;
vector<string> names,ans;
map<string,int> visit;
int main(int argc,char * argv[]) {
	int m,n,s;
	scanf("%d%d%d",&m,&n,&s);
	names.resize(m+1);
	for(int i=1; i<=m; i++)
		cin>>names[i];
	int j=s;
	while(j<=m) {
		if(visit[names[j]]==1) {
			j++;
			continue;
		}
		visit[names[j]]=1;//标记已获奖
		ans.push_back(names[j]); //存入结果队列
		j+=n;
	}
	if(ans.size()==0)printf("Keep going...
");
	else {
		for(int i=0; i<ans.size(); i++) {
			printf("%s
",ans[i].c_str());
		}
	}
	return 0;
}

Code 02

#include <iostream>
#include <map>
using namespace std;
int main() {
	int m, n, s;
	scanf("%d%d%d", &m, &n, &s);
	string str;
	map<string, int> mapp;
	bool flag = false;
	for (int i = 1; i <= m; i++) {
		cin >> str;
		if (mapp[str] == 1) {
			s = s + 1;
		} else if (i == s && mapp[str] == 0) {
			mapp[str] = 1;
			cout << str << endl;
			flag = true;
			s = s + n;
		}
	}
	if (flag == false) cout << "Keep going...";
	return 0;
}