PAT A1124 Raffle for Weibo Followers(C++)

PAT甲级目录 | PAT乙级目录

题目描述

原题地址:A1124 Raffle for Weibo Followers
中文版:B1069 微博转发抽奖

解题思路

模拟题。用 map 来记录中奖账号,并设置一个锚点指示下一个中奖编号,当遍历到该中奖编号。若该账户已经中过奖,则跳过此账号且锚点后移一位;若未中奖,则输出中奖信息,且将该账号录入 map 数组。

易错点

  • 遇到中过奖的账号要跳过,顺次取其下一位。

也许陌生的知识点

  • map<string, int> h;
    • 用于映射,键和值可以是任意类型
    • 直接使用 m[<键>] = <值> 即可向map中添加一组键值对
    • 需要的头文件:map
  • if(h.find(id1) == h.end()){ }
    • h.find(x) 函数可用于查找序列中是否有某元素,如找到则返回元素迭代器,如未找到则返回 h.end()
    • 包含该函数的容器:map, set

代码示例:

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
#include <cstdio>
#include <iostream>
#include <vector>
#include <map>
#include <string>
using namespace std;
int main() {
int m, n, s, flag = 0;
string temp;
map<string, int> h;
scanf("%d %d %d", &m, &n, &s);
int next = s; // 锚点,用于指示下一个中奖编号
for(int i = 1; i <= m; i++){
cin >> temp;
if(i == next){
if(h.find(temp) == h.end()){// 没过中奖,则中将
h[temp] = 1;
cout << temp << endl;
next += n;
flag = 1;
} else next++; // 已经中过奖,编号后移一位
}
}
if(flag == 0) cout << "Keep going..." << endl;
return 0;
}