#PQJ2589x15061. QOJ 2589_15061

    ID: 2842 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:JSOI 2014

QOJ 2589_15061

NOI 2014 江苏代表队分组赛

第一试学生选课 学生选课 【问题描述】 进入大学以后,学生们将面临选课,有N 个学生需要选课,学校里有三个 老师JYY,YJY,YYJ。第一年里,每个学生们都选择了其中一位老师。 经过了一年的学习,学生之间相互都有一定的印象,每个同学会根据自己的 印象给另外N-1 个学生从好到坏排序。第二年的选课开始了,每个学生需要选择 老师,可能是因为被坑多了,每一位同学都想换一个老师。这时需要你来调度同 学们选课,使得上同一堂课的学生之间印象最坏的最好。 【输入格式】 从文件student.in 中读入数据。 输入文件第一行包含一个整数N。 第2 到N+1 行,每行有N 个正整数。 其中第i+1 行提供第i 个同学的信息,其中第一个整数Ai,值为0,1,2 中的 一个,表示第一年第i 个同学选的老师。接下来N-1 个数字,是1,2,…,i-1,i+1,…,N 的一个排列,表示第i 个同学对其他同学印象从好到坏的排序。 【输出格式】 输出到文件student.out 中。 输出文件包含一行一个整数,为最小的非负整数T,满足: 1、所有同学选择了和第一年不同的老师。 2、所有选择同一个老师的学生间彼此印象都是前T 好的。 具体细节见样例。 【输入样例1】 6 0 2 3 4 5 6 0 1 3 4 5 6 1 6 5 4 2 1 2 6 5 3 2 1 1 1 2 3 4 6 2 1 2 3 4 5 【输出样例1】 4

NOI 2014 江苏代表队分组赛

第一试学生选课 【输入样例2】 3 0 2 3 1 1 3 2 1 2 【输出样例2】 0 【样例说明】 对于第一个样例,六名同学分别选择老师1,2,0,0,2,0。此时老师0 的课中同学六对同学四的印象为第4 好,所以答案T 为4。并且找不到更小的T。 对于第二个样例,把所有同学分到不同的班级里,则T 为0。 【数据规模】 对于30%的数据满足N≤20 对于60%的数据满足N≤100 对于100%的数据满足N≤1000