当前位置: 代码迷 >> 综合 >> Luogu P1803
  详细解决方案

Luogu P1803

热度:99   发布时间:2023-12-05 05:33:11.0

利用类进行排序:

        CLASS必为STATIC 因为要被MAIN 调用,STATIC 类只能调用外部STATIC类

        CLASS内可以包含多个变量

利用ARRAYS.SORT排序:
        

public static class cmp implements Comparator<exam>/*自己创建的类,例子里是exam*/>{@Overridepublic int compare(exam a, exam b) {if (a.e > b.e) {return 1;}else if (a.e == b.e) {return 0;}else {return - 1;}}}Arrays.sort("待排数组", new cmp());
//如果需要重排int, char等primitive, 需要用对应的Class Integer, Character...

思路:
        每次考试的结束时间越早,我们将他越早排入列表,因为其对随后的考试影响最小。

        因此,首先对所有考试以结束时间进行升序排序,然后依次判断下一个考试开始时间是否冲突,若冲突则继续顺延。保证了结束时间早的被优先考虑。

CODE:

public static void main(String[] args) throws IOException {StreamTokenizer re = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));re.nextToken();int n = (int) re.nval;exam[] exs = new exam[n];for (int i = 0; i < n; i++) {exs[i] = new exam();re.nextToken();exs[i].s = (int) re.nval;re.nextToken();exs[i].e = (int) re.nval;//exs[i] = tmp;}Arrays.sort(exs, new cmp());//qs(0, n - 1);int flag = 1;int end = exs[0].e;int cnt = 1;while(flag <= n - 1) {if (exs[flag].s >= end) {cnt++;end = exs[flag].e;}flag++;}System.out.printf("%d", cnt);//sc.close();}
}