公平摄影

题目

链接：1913. 公平摄影 - AcWing题库

农夫约翰的 N 头奶牛站在一维长围栏的不同位置。

第 i 头牛位于位置 xi，其所属品种为 bi（根西岛牛或荷斯坦牛）。

所有奶牛的位置各不相同。

约翰想给一段连续区间内的奶牛拍摄一张照片，用来在乡村集市上展览。

但是我们希望他所有品种的奶牛都能在照片中得到公平的展示。

因此，他希望确保无论照片中出现哪些品种的奶牛，每种品种的奶牛在照片中的数量都必须相等。

例如，一张照片中只包含荷斯坦牛是可以的，包含荷斯坦牛和根西岛牛各 27 头也没问题，但是包含 10 头荷斯坦牛和 9 头根西岛牛则不可以。

请确定，约翰可以拍下的满足以上条件的照片的最大尺寸。

照片的尺寸是指照片中奶牛最大和最小位置之间的差。

约翰最终可能只拍下一头奶牛，这种情况下，照片尺寸为 0。

代码

import java.util.*;


public class Main {
    static int N = 100010;
    static int n;
    static node[] q = new node[N];
    static TreeMap<Integer, Integer> m = new TreeMap<>();
    public static void main(String[] args) {
        Scanner inScanner = new Scanner(System.in);
        n = inScanner.nextInt();
        for(int i = 1; i <= n; i ++)
        {
            int x = inScanner.nextInt();
            String s;
            s = inScanner.next();
            if(s.equals("G"))
                q[i] = new node(x, 1);
            else
                q[i] = new node(x, -1);
        }
        Arrays.sort(q, 1, n + 1);
        int ans = 0, sum = 0, pre = 0;
        for(int i = 1; i <= n; i ++)
        {
            if(!m.containsKey(sum))
                m.put(sum, q[i].x);
            sum += q[i].y;
            if(m.containsKey(sum))
                ans = Math.max(ans, q[i].x - m.get(sum));
            if(i == 1 || q[i].y != q[i - 1].y)  
                pre = q[i].x;
            ans = Math.max(ans, q[i].x - pre);
        }
        System.out.println(ans);
    }
}
class node implements Comparable<node>
{
    int x;
    int y;
    public node(int x, int y)
    {
        this.x = x;
        this.y = y;
    }
    @Override
    public int compareTo(node o) {
        return x - o.x;
    }
}