一锅炖不下的博客
D - HomeGarden——atcoder379
一锅炖不下
  2024-11-12 20:14:27   2024-11-12 21:34:23

D - Home Garden

几个问题：

  • 怎么做区间加法？怎么快速为当前所有值加上一个数？
  • 怎么快速获取大于H的所有值？并且动态地删除这些值？
  • 怎么同时满足以上两个条件？

看了答案……牛逼，用一个队列就做出来了，这个解法巧妙的地方在于它没有用我上面的思路，它不是更新所有植物的高度，而是更新grow值。并且植物的初始高度设为-grow，这样相当于前面累积的grow值被抵消了，只有后续的生长值才对它起作用。收割的时候，也不直接用h来比较，而是用h - grow的差值来与植物的高度比较。

突然想到，也可以不用h - grow，可以改成：

1
2
3
4
5
6
7
8
case 3:
    long h = sc.nextInt();
    int ans = 0;
    while (!plants.isEmpty() && plants.peek() + grow >= h) {
        plants.poll();
        ans++;
    }
    System.out.println(ans);

其实这也是延迟更新的一种思路吧，既然只在比较时才用到植物的高度，那么就先把这段时间的更新值记录起来，等到要取出来比较的时候再加上就可以了。

用队列也是非常合适的，因为前面种的植物肯定长得更高，也会更先被收割。

总结一下，之后遇到题目可以有哪些思考方向呢？

  • 怎样判断是否有先进先出的特性？——有时这种特性是隐含的，比如像这道题，先种的植物先收割，就是一个需要被发掘的隐藏条件。所以选择数据结构之前一定要充分挖掘数据的特性。
  • 延迟更新的思路——如果下次再遇到这种一次需要更新大量数据，但只在查询时会用到更新后的值时，可以先不急着更新，只在查询访问到的时候更新一次。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class HomeGarden {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int Q = sc.nextInt();
        Queue<Long> plants = new LinkedList<>();
        long grow = 0;
        for (int i = 0; i < Q; i++) {
            int op = sc.nextInt();
            switch (op) {
                case 1:
                    plants.offer(-grow);
                    break;
                case 2:
                    int t = sc.nextInt();
                    grow += t;
                    break;
                case 3:
                    long h = sc.nextInt();
                    h -= grow;
                    int ans = 0;
                    while (!plants.isEmpty() && plants.peek() >= h) {
                        plants.poll();
                        ans++;
                    }
                    System.out.println(ans);
            }
        }
    }
}