【Java版oj】day35年会抽奖、抄送列表

刺骨的言语ヽ痛彻心扉 2024-03-23 14:12 50阅读 0赞

**目录**

一、年会抽奖

（1）原题再现

（2）问题分析

（3）完整代码

二、抄送列表

（1）原题再现

（2）问题分析

（3）完整代码

--------------------

> ## 一、年会抽奖 ##
> 
> ### （1）原题再现 ###
> 
> [年会抽奖\_\_牛客网][Link 1]
> 
> 今年公司年会的奖品特别给力，但获奖的规矩却很奇葩：  
> 1. 首先，所有人员都将一张写有自己名字的字条放入抽奖箱中；  
> 2. 待所有字条加入完毕，每人从箱中取一个字条；  
> 3. 如果抽到的字条上写的就是自己的名字，那么“恭喜你，中奖了！”  
> 现在告诉你参加晚会的人数，请你计算有多少概率会出现无人获奖？
> 
> **输入描述:**
> 
> 输入包含多组数据，每组数据包含一个正整数n（2≤n≤20）。
> 
> **输出描述**对应每一组数据，以“xx.xx%”的格式输出发生无人获奖的概率。
> 
> 示例1
> 
> 输入
> 
> 2
> 
> 输出
> 
> 50.00%
> 
> ### （2）问题分析 ###
> 
> 这个题目没有想象的简单，n个人取到的都不是自己名字的概率=n个人取到的不是自己名字的序列个数 / n个人可能抽取的所有可能性。
> 
> 首先：.n个人可能抽取的所有结果是**n的阶乘**![\\AA \_\{n\}^\{n\}][AA _n_n]**（比如三个人，甲先从3张中抽，乙再从2张中抽，丙最后从1张里抽，所有可能的结果为3\*2\*1=6）**
> 
> 其次：n个人抽到不是自己的序列个数。假设第一个人抽到的不是自己的个数![C\_\{n-1\}^\{1\}][C_n-1_1]；假设第二个人这个时候拿到了第一个人的名字，那么对于第二个人的名字有两种情况：第一种：第二个人的名字是被第一个人拿到了，也就是甲和乙互相拿了对方的名字，那么对于其他的n-1个人来说互相拿错是一个规模n-2的子问题 ；第二种：第二个人的名字没有被第一个人拿到，则剩下的问题是规模n-1的子问题。
> 
> ![f(n)=C\_\{n-1\}^\{1\}\*(f(n-2)+f(n-1))][f_n_C_n-1_1_f_n-2_f_n-1]
> 
> ### （3）完整代码 ###
> 
>     import java.util.Scanner;
>     
>     public class Main {
>         public static void main(String[] args) {
>             Scanner sc = new Scanner(System.in);
>             while (sc.hasNextInt()) {
>                 double num = sc.nextInt();
>                 double ans = error(num) / all(num);
>                 System.out.format("%.2f", ans * 100);
>                 System.out.println("%");
>             }
>         }
>         //所有可能的情况
>         public static double all(double num) {
>             double ans = 1;
>             for (int i = 1; i <= num; i++) {
>                 ans *= i;
>             }
>             return ans;
>         }
>         //拿错的情况
>         public static double error(double num) {
>             if (num == 1) {
>                 return 0;
>             }
>             if (num == 2) {
>                 return 1;
>             }
>             return (num-1)*(error(num - 2) + error(num - 1));
>         }
>     }
> 
> ![31ccf01a64244eacabda93f8c4d7087c.png][]

> ## 二、抄送列表 ##
> 
> ### （1）原题再现 ###
> 
> [抄送列表\_\_牛客网][Link 2]
> 
> NowCoder每天要处理许多邮件，但他并不是在收件人列表中，有时候只是被抄送。他认为这些抄送的邮件重要性比自己在收件人列表里的邮件低，因此他要过滤掉这些次要的邮件，优先处理重要的邮件。  
> 现在给你一串抄送列表，请你判断目标用户是否在抄送列表中。
> 
> **输入描述:**
> 
> 输入有多组数据，每组数据有两行。 第一行抄送列表，姓名之间用一个逗号隔开。如果姓名中包含空格或逗号，则姓名包含在双引号里。总长度不超过512个字符。 第二行只包含一个姓名，是待查找的用户的名字（姓名要完全匹配）。长度不超过16个字符。
> 
> **输出描述:**
> 
> 如果第二行的名字出现在收件人列表中，则输出“Ignore”，表示这封邮件不重要；否则，输出“Important!”，表示这封邮件需要被优先处理。
> 
> 示例1
> 
> 输入
> 
> Joe,Kewell,Leon
> 
> Joe
> 
> "Letendre, Bruce",Joe,"Quan, William"
> 
> William
> 
> 输出
> 
> Ignore
> 
> Important!
> 
> ### （2）问题分析 ###
> 
> 给出几个样例感受一下
> 
> **1）"Zhang Joe","Zhang, Joe",Kewell  
> Joe  
> 2）"Zhang Joe","Zhang, Joe",Kewell  
> Zhang Joe  
> 3）"Zhang Joe","Zhang, Joe",Kewell  
> Zhang,Joe  
> 4）"Zhang Joe","Zhang, Joe",Kewell  
> Zhang, Joe  
> 5）"Zhang Joe","Zhang, Joe",Kewell  
> Zhang ,Joe  
> 6）"Zhang Joe","Zhang, Joe",Kewell  
> Kewel  
> 7）"Zhang Joe","Zhang, Joe",Kewell  
> Kewell**
> 
> **1）Important!  
> 2）Ignore  
> 3）Important!  
> 4）Ignore  
> 5）Important!  
> 6）Important!  
> 7）Ignore**  
> 
> 
> 姓名有两种方式表示，一种是姓名中包含空格或逗号，则姓名包含在双引号里；另一种是没有引号的。所有我们可以使用指针法，首先定义一个指针fast，判断fast指针指向的位置是否是引号。**如果fast指向引号**，则从fast指针的后一个位置开始寻找下一个引号的位置**，然后将中间引号包含的字符串放入集合，因为给出的一个名字是不包含引号的。fast指针指向下一个位置，fast=end+2,去掉第二个引号和两个名字之间的逗号。如果fast不指向引号**，则从fast指针的后一个位置开始寻找下一个逗号的位置**，然后将中间逗号包含的字符串放入集合。fast指针指向下一个位置，fast=end+1,去掉两个名字之间的逗号。**
> 
> ### （3）完整代码 ###
> 
>     import java.util.*;
>     /*
>     *抄送列表
>     */
>     public class Main {
>         public static void main(String[] args) {
>             Scanner scan = new Scanner(System.in);
>             while (scan.hasNext()) {
>                 String name = scan.nextLine();
>                 int fast = 0;
>                 Set<String> s = new HashSet<>();
>                 while (fast < name.length()) {
>                     if (name.charAt(fast) == '\"') {
>                         int end = name.indexOf('\"', fast + 1);
>                         String tmp = name.substring(fast + 1, end);
>                         s.add(tmp);
>                         fast = end + 2;
>                     } else {
>                         int end = name.indexOf(',', fast + 1);
>                         if (end == -1) {
>                             end = name.length() - 1;
>                             s.add(name.substring(fast, end + 1));
>                             break;
>                         }
>                         String tmp = name.substring(fast, end);
>                         s.add(tmp);
>                         fast = end + 1;
>                     }
>                 }
>                 name = scan.nextLine();
>                 if (s.contains(name) == true) {
>                     System.out.println("Ignore");
>                 } else {
>                     System.out.println("Important!");
>                 }
>             }
>         }
>     }
> 
> ![6eb75b256edf4bdbab736cc9f4307844.png][]

--------------------

![8c185de82b2b4deab8a5d5745d0ad1c0.png][]

[Link 1]: https://www.nowcoder.com/questionTerminal/610e6c0387a0401fb96675f58cda8559
[AA _n_n]: https://latex.csdn.net/eq?%5CAA%20_%7Bn%7D%5E%7Bn%7D
[C_n-1_1]: https://latex.csdn.net/eq?C_%7Bn-1%7D%5E%7B1%7D
[f_n_C_n-1_1_f_n-2_f_n-1]: https://latex.csdn.net/eq?f%28n%29%3DC_%7Bn-1%7D%5E%7B1%7D*%28f%28n-2%29&plus;f%28n-1%29%29
[31ccf01a64244eacabda93f8c4d7087c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/2ad568eea84143f4b42bb8d19bbb80cf.png
[Link 2]: https://www.nowcoder.com/questionTerminal/286af664b17243deb745f69138f8a800
[6eb75b256edf4bdbab736cc9f4307844.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/9174fe72da8f42fe8b5c35ba92984ee8.png
[8c185de82b2b4deab8a5d5745d0ad1c0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/6f36ea85909f44e186547e7399bfb6de.png