Java教程

1124 Raffle for Weibo Followers (20 分)

本文主要是介绍1124 Raffle for Weibo Followers (20 分),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

1. 题目

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

Sample Output 2:

Keep going...

2. 题意

John进行转发抽奖活动,给出三位正整数M,N,S,分别表示转发的总人数、小明决定的中奖间隔、以及第一名中奖者的序号(编号从1开始)。每位网友可能多次转发,但只能中一次奖。如果处于当前位置的网友中过奖,则一直顺延到下一位没有中奖的网友。

3. 思路——模拟+map

  1. 如果第1位中奖者的序号大于转发总人数,说明没人中奖,直接输出return 0即可。
  2. 否则从第1位中奖者S开始,每N位产生一名中奖者:如果该名网友先前中奖过,那么就顺延给下一位没有中奖的网友;否则就输出该名中奖者的网名,并将其置为中奖过的状态!
  • 错误总结:
    • 这题我自己因为没有理解对题目意思,所以卡了很久,刚开始题目有点没看懂,这是硬伤,后面看了翻译,又理解错了题目,以为顺延值顺延一位,没有想到顺延那一位如果也中奖过再往下顺延的情况。综上理解,导致卡了很久,题目本身并不难。
    • 还有就是刚开始想到用set来判断网友有没有中奖过,但是这比起使用map麻烦很多,所以选择正确的数据结构很有必要!

4. 代码

#include <iostream>
#include <map>
#include <string>

using namespace std;

int main()
{
	int m, n, s;
	cin >> m >> n >> s;
	map<string, int> res;
	string names[m + 1];
	for (int i = 1; i <= m; ++i) 
		cin >> names[i];
		
	if (s > m) // 如果第一位获胜者的位数大于转发总数,说明没有获胜者 
		cout << "Keep going..." << endl;

	// 从第一位获胜者s开始,每间隔n位产生一名获胜者 
	for (int i = s; i <= m; i += n)
	{
		if (res[names[i]] == 1) // 如果这位获胜者已经拿过一次奖了 
		{ 
			i++;	// 那么开始顺延给下一位 
			while (i <= m)	// 一直顺延,直到没有获奖过之前都没获奖过的那一位 
			{
				if (res[names[i]] == 0)  
				{
					cout << names[i] << endl;
					res[names[i]] = 1; 
					break;
				}
				i++;
			}
		} else	// 如果这位获胜者未获过奖,则输出 
		{
			cout << names[i] << endl;
			res[names[i]] = 1;
		}
	
	}
	return 0;
}
这篇关于1124 Raffle for Weibo Followers (20 分)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!