CodinGame - GRAFFITI ON THE FENCE 思路

末蓝、 2023-07-10 11:17 2阅读 0赞

题目来源：[CodinGame Graffiti on the fence][]

## 要求 ##

`L`代表篱笆长度，`N`代表输入数据的组数，每组数据中`st`代表开始粉刷位置，`ed`代表结束位置

*  1 ≤ `L`≤ 2,000,000,000
 *  1 ≤ `N`≤ 100
 *  0 ≤ `st` < `ed`≤`L`
 *  全粉刷输出`All painted`
 *  输出未粉刷的位置，包含开始与结束位置

## 思路 ##

用数组代表篱笆会造成内存浪费，因此用数组存储粉刷位置，排序后计算得出未粉刷位置。用布尔变量标识是否粉刷，若未粉刷，则表示全粉刷。

## 代码 ##

import java.util.*;
    import java.io.*;
    import java.math.*;
    
    class Solution { 
    
        public static void main(String args[]) { 
            Scanner in = new Scanner(System.in);
            int L = in.nextInt();
            int N = in.nextInt();
            //System.err.println(L);//
            //System.err.println(N);//
            boolean painted = false;
            List<Info> list = new ArrayList<>();
            for (int i = 0; i < N; i++) { 
                int st = in.nextInt();
                int ed = in.nextInt();
                list.add(new Info(st,ed));
                //System.err.println("input:"+st+" "+ed);//
            }
            Collections.sort(list);
            //System.err.println(list);//
            long last = 0 ;
            for (Info i:list){ 
                if (i == list.get(0) && i.st == 0){ 
                    last=i.ed;
                    continue;
                }
                if (last < i.st){ 
                    System.out.println(last+" "+i.st);
                    painted = true;
                }
    
                if (last< i.ed)
                    last = i.ed;
                if (i == list.get(list.size()-1) && i.ed!=L){ 
                    painted = true;
                    System.out.println(last+" "+L);
                }
            }
            if (!painted){ 
                System.out.println("All painted");
            }
        }
    }
    
    class Info implements Comparable<Info>{ 
        long st,ed;
        public Info(long st,long ed){ 
            this.st = st;
            this.ed = ed;
        }
    
        @Override
        public int compareTo(Info info) { 
            if (this.st > info.st)
                return 1;
            else if (this.st < info.st)
                return -1;
            else return 0;
        }
    
        @Override
        public String toString() { 
            return "{" +
                    "st=" + st +
                    ", ed=" + ed +
                    '}';
        }
    }

[CodinGame Graffiti on the fence]: https://www.codingame.com/ide/puzzle/graffiti-on-the-fence