SowingStones——atcoder379

Sowing Stones

第一想法是用栈来做。然后想栈和队列结合起来做，栈内保存石子数大于1的格子的下标，用于从最近的溢出格子中移动石子；队列保存格子下标，用于判断区间内的石子数量是否足够。但是这样做有点问题。如下：

有几个问题：

• 怎样一个区间一个区间地判断石子的数量是否足够？因为如果一个区间的石子不够，但如果再往前有多余的石子，也可以挪到后面。这一点有点不好操作。
• 怎样计算操作数？

去看了其他人通过的答案，感觉挺巧妙的，巧妙之处在于这种做法用一个top变量，既控制了每次小区间的右边界，最后又用它的正负判断了石子是否足够。

我能从这道题中学到什么，有没有什么可以迁移到其他问题的思路，几个启发式的方法：

• 思考个问题题的数据是否有某种内在的顺序——例如这道题，后续加入的石子，它的坐标一定是更靠后的
• 思考遍历的顺序——不一定是从小到大遍历，有时也会反向，也可能从中间向两边，从两边向中间
• 思考一个变量是否能表达更多的含义——例如它小于零的时候代表什么，大于零的时候代表什么
• 思考是否可以用整体的思路降低问题的复杂度——例如这道题如果每个存在空格的区间都判断石子是否足够的话，复杂度就过高了，而如果整体来做的话，就没那么高
• 思考有没有什么数学方法可以简化问题

public class SowingStones {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long N = sc.nextLong();
        int M = sc.nextInt();
        // 为什么用TreeMap?
        // 1. TreeMap可以用较少的空间保存类似这种比较稀疏的数据
        // 2. TreeMap是红黑树，本身是一种搜索数，提供了descendingKeySet api，支持区间边界从大到小遍历
        TreeMap<Long, Long> xToA = new TreeMap<>();
        long[] X = new long[M];

        for (int i = 0; i < M; i++) {
            X[i] = sc.nextLong();
        }

        for (int i = 0; i < M; i++) {
            xToA.put(X[i], sc.nextLong());
        }

        long count = 0;
        long top = N;
        for (long x : xToA.descendingKeySet()) {
            long a = xToA.get(x);
            // 这里检查石子溢出的情况
            if (top - x + 1 >= a) {
                // 用等差数列和计算每个空白区间内的移动步数
                // 相当于把每个石子都一一移到当前区间的右端
                count += a * (2 * top - 2 * x - a + 1) / 2;
                // 更新top
                top -= a;
            } else {
                System.out.println(-1);
                return;
            }
            if (top <= 0) {
                break;
            }
        }
        // 如果最终top大于0，说明石子不够装满所有格子
        if (top > 0) {
            System.out.println(-1);
            return;
        }
        System.out.println(count);
    }
}