金发姑娘和N头牛

题目

链接：1952. 金发姑娘和 N 头牛 - AcWing题库

你可能听过关于金发姑娘和三只熊的经典故事。

然而，鲜为人知的是，金发姑娘最终成了一个农民。

在她的农场中，她的牛棚里有 N 头奶牛。

不幸的是，她的奶牛对温度相当敏感。

对于奶牛 i，使其感到舒适的温度为 Ai…Bi。

如果金发姑娘将牛棚的恒温器的温度 TT 设置为 T<Ai，奶牛就会觉得冷，并会产出 X 单位的牛奶。

如果她将恒温器的温度 T 设置在 Ai≤T≤Bi，奶牛就会感到舒适，并会产出 Y 单位的牛奶。

如果她将恒温器的温度 TT 设置为 T>Bi，奶牛就会觉得热，并会产出 Z 单位的牛奶。

正如所期望的那样，Y 的值始终大于 X 和 Z。

给定 X,Y,Z 以及每头奶牛感到舒适的温度范围，请计算通过合理设定恒温器温度，金发姑娘可获得的最大产奶量。

恒温器温度可设置为任何整数。

代码

import java.util.*;


public class Main {
    static int n, x, y, z;
    static TreeMap<Integer, Integer> m = new TreeMap<Integer, Integer>();
    public static void main(String[] args) {
        Scanner inScanner = new Scanner(System.in);
        n = inScanner.nextInt();
        x = inScanner.nextInt();
        y = inScanner.nextInt();
        z = inScanner.nextInt();
        int r = 0;
        for(int i = 1; i <= n; i ++)
        {
            int ll, lr;
            ll = inScanner.nextInt();
            lr = inScanner.nextInt();
            r = Math.max(r, lr + 1);
            m.put(0, m.getOrDefault(0, 0) + x);
            m.put(ll, m.getOrDefault(ll, 0) + y - x);
            m.put(lr + 1, m.getOrDefault(lr + 1, 0) - y + z);
        }
        inScanner.close();
        long ans = 0, sum = 0;
        Collection<Integer> value = m.values();
        for(Integer i : value)
        {
            sum += i;
            if(ans < sum)
                ans = sum;
        }
        System.out.println(ans);
    }
}
/*
4 7 9 6
5 8
3 4
13 20
7 10
*/

import java.util.*;


public class Main {
    static int n, x, y, z;
    static int[] l = new int[20010];
    static int[] r = new int[20010];
    static int[] b = new int[40010];
    static Vector<Integer> v = new Vector<>();
    public static int find(int t)
    {
        int l = 0, r = v.size() - 1;
        while(l < r)
        {
            int mid = l + r >> 1;
            if(t > v.get(mid))
                l = mid + 1;
            else
                r = mid;
        }
        return r;
    }
    public static void main(String[] args) {
        Scanner inScanner = new Scanner(System.in);
        n = inScanner.nextInt();
        x = inScanner.nextInt();
        y = inScanner.nextInt();
        z = inScanner.nextInt();
        for(int i = 1; i <= n; i ++)
        {
            l[i] = inScanner.nextInt();
            r[i] = inScanner.nextInt();
            if(!v.contains(l[i]))
                v.add(l[i]);
            if(!v.contains(r[i]))
                v.add(r[i]);
        }
        v.add(Integer.MIN_VALUE);
        v.add(Integer.MAX_VALUE);
        Collections.sort(v);
        inScanner.close();
        int ll = v.size() - 1;
        for(int i = 1; i <= n; i ++)
        {
            int L = find(l[i]), R = find(r[i]);
            b[0] += x;
            b[L] += y -x;
            b[R + 1] += z - y;
            b[ll] -= z;
        }
        long ans = 0, sum = 0;
        for(int i = 0; i <= ll; i ++)
        {
            sum += b[i];
            if(sum > ans)
                ans = sum;
        }
        System.out.println(ans);
    }
}
/*
4 7 9 6
5 8
3 4
13 20
7 10
*/