题意:给出3N个点,删除其中N个点,将剩下的2N个数分成两份,求前面部分的和减去后面部分的和的最大值.
题解:设前面部分为Na,后面部分为Nb,要使Na-Nb最大.我们可以先假设这删除的N个全都是从N+1到3N中删除的.那么Na最大的就是前面N个的和,我们用最小优先队列来维护这N个的值,然后把接下来的第N+1个数push 进去,删除其中最小的这样就得到了在前N+1个中删除一个的前面的最大值了,依次类推.同理,我们用一个最大优先队列维护后面的N个值,然后往前推,这样就得到了每个区间Nb的最小值.最后循环一遍取Nai-Nbi的最大值就好.
priority_queue r;