[ARC196A] Adjacent Delete 题解

Getaway_Car
  2025-04-10 12:00 2025-04-10 12:00 Created   2026-01-19 20:04:21 2026-01-19 20:04:21 Updated      186 Words  1 Mins

假设 是偶数。如果我们忽略删除相邻数的条件，即可以任选两个数相减，那么答案应该是前 大的数（记作“较大数”）的和减去前 小的数（记作“较小数”）的和。

容易发现，当我们只能选相邻的数相减时，依然可以达到这个答案，因为在任意时刻，总存在至少一对较大数与较小数相邻。

当 是奇数，那么一定有一个元素不被选，且这个元素一定在奇数位，这样才能把数组分成长度为偶数的两段。枚举不被选的位置，用对顶堆维护前后两段的答案即可。

时间复杂度 。

提交记录

  • Title: [ARC196A] Adjacent Delete 题解
  • Author: Getaway_Car
  • Created at : 2025-04-10 12:00:00
  • Updated at : 2026-01-19 20:04:21
  • Link: https://getawaycar1024.github.io/article/ARC196A-Adjacent-Delete-题解/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
[ARC196A] Adjacent Delete 题解