PAT 乙级 1059

题目

题解

开始我是从暴力循环的角度考虑这道题，大概计算了一下时间复杂度应该不会超，但是很不幸没有通过，时间超限；之后考虑搜索算法可能优化不太好，因此就把输入的序列先排序，之后用了二分查找，结果复杂度还是超（现在想想，实际上暴力循环和先排序后二分的复杂度差不多）；

通过的方法是通过输入的ID号作为数组的下标，那么在查找的过程中就简化为线性，O(1)的复杂度就不会存在任何问题，同时只需要通过整数类型的数组和bool类型的数组就能解决所有访问问题，与之前的结构体存储的复杂度完全不是一个量级，这是一个非常好的思路；再加上之前做的一道题，学习了一种新的输出控制方式，因此也能够通过int类型方式输出题目规定的格式；

通过这道题主要学到以下几点：

1. 暴力循环不是解决问题的唯一方式，做题的过程中考虑一下是否能通过下标定位的方式，思考问题的方式不要过于单一；

2. 判断素数的循环条件需要特别注意

 for (int i = ; i <= sqrt(n); i++) {        //注意循环结束条件是<=

     if (n % i == )

         return false;

 }

 return true;

3. 输出过程中位数不够需要补0，那么可以使用printf格式控制符，printf("%04d\n", num); //输出num不足4位在之前补0

代码

 #include <iostream>

 #include <cmath>

 using namespace std;

 bool prime(int n) {

     if (n == )

         return true;

     else{

         for (int i = ; i <= sqrt(n); i++) {

             if (n % i == )

                 return false;

         }

     }

     return true;

 }

 int main() {

     int n = , k  = , tmp = ;

     int stu[] = {  };

     bool flag[] = {  };

     cin >> n;

     for (int i = ; i <= n; i++) {

         cin >> tmp;

         stu[tmp] = i;

     }

     cin >> k;

     for (int i = ; i < k; i++) {

         cin >> tmp;

         if (stu[tmp] == )

             printf("%04d: Are you kidding?\n", tmp);

         else if (stu[tmp] ==  && !flag[tmp]) {

             printf("%04d: Mystery Award\n", tmp);

             flag[tmp] = true;

         }

         else if (prime(stu[tmp]) && !flag[tmp]) {

             printf("%04d: Minion\n", tmp);

             flag[tmp] = true;

         }

         else if (!prime(stu[tmp]) && !flag[tmp]) {

             printf("%04d: Chocolate\n", tmp);

             flag[tmp] = true;

         }

         else

             printf("%04d: Checked\n", tmp);

     }

     return ;

 }

巴特西

PAT 乙级 1059

题目

题解

代码

最新文章

热门文章