[ARC196A] Adjacent Delete 题解

Getaway_Car

2025-04-10 12:00 2025-04-10 12:00 Creado 2025-04-12 21:33:49 2025-04-12 21:33:49 Actualizado

186 Palabras 1 Minutos

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

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

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

时间复杂度。

Título: [ARC196A] Adjacent Delete 题解
Autor: Getaway_Car
Creado el : 2025-04-10 12:00:00
Actualizado el : 2025-04-12 21:33:49
Enlace: https://getawaycar1024.github.io/article/ARC196A-Adjacent-Delete-题解/
Licencia: Este trabajo está licenciado bajo CC BY-NC-SA 4.0.

Comentarios