PTA 乙级 1059 C语言竞赛 (20分)

2021-03-30 21:28

阅读：761

标签：std min 乙级检查 image pac clu return pre

技术图片

看见时间限制200ms，必然有猫腻（运行超时）

如果查询的时候用遍历的方法一个个对应，必然会超时

所以，建立一个足够大的数组，ID对应数组角标，存储ID的排名和确定是否被检查过(int id[10001][2])

判断是否为素数，用平方根的方法判断，缩短运算速度（1013数素数）

1 bool isPrime(int num) {
2     for (int i = 2; i i) {
3         if (num % i == 0) {
4             return 0;
5         }
6     }
7     return 1;
8 }

二维数组[0]存储名次，[1]存储是否被检查的标志位

 1 #include 2 #include 3 #include 4 
 5 using namespace std;
 6 
 7 int id[10001][2] = { 0 };
 8 
 9 bool isPrime(int num) {                        //判断是否为素数
10     for (int i = 2; i i) 
11         if (num % i == 0) return 0;
12     return 1;
13 }
14 
15 int main() {
16     int n = 0, k = 0;
17     cin >> n;
18     for (int i = 0; i i) {
19         int tmp = 0;
20         cin >> tmp;                            
21         id[tmp][0] = i + 1;                            //对应id存储对应名次
22     }
23     cin >> k;
24     for (int i = 0; i i) {
25         int fid = 0;
26         cin >> fid;
27         printf("%04d: ", fid);                        //保证四位，空位补零
28         if (id[fid][0] == 0)                        //没有对应名次
29             cout "Are you kidding?"  endl;
30         else if (id[fid][1] == 0) {                    //未被检查过
31             if (id[fid][0] == 1) cout "Mystery Award"  endl;
32             else if (isPrime(id[fid][0])) cout "Minion"  endl;
33             else cout "Chocolate"  endl;
34             id[fid][1] = 1;                            //确认是否被检查的标志位置1
35         }
36         else
37             cout "Checked"  endl;
38         
39     }
40     return 0;
41 }