十月的最后一天。
CCO2020 Exercise Deadlines
交换次数等于逆序对数量,所以我们的目标就是最小化逆序对数量。
考虑一个贪心,每次将尽可能大的数放在最后面。用线段树/树状数组来维护即可。
「雅礼集训 2017 Day4」洗衣服
有一个做法是分别处理洗完每件衣服的最少时间 \(a_i\),和烘干每件衣服的最少时间 \(b_i\),然后将 \(a\) 从小到大与 \(b\) 从大到小匹配,求最大值。
为什么是对的?先来考虑 \(a_i+b_i\) 的含义,实际上是在 \(a_i\) 的时间洗完衣服后,还会再使用 \(b_i\) 的时间使用烘干机,这里烘干机的使用也包括后面接上的。
对于被同一个烘干机烘干的两件相邻的衣服 \(x\) 和 \(y\),若 \(a_{x}+d\ge a{y}\),此时就是 \(a_x\) 造成贡献;否则若 \(a_{x}+d<a_y\) 此时就是 \(a_y\) 造成贡献。
就相当于取最大值。
待补。
标签:10,衣服,31,2024,烘干机,逆序 From: https://www.cnblogs.com/ddxrS/p/18518907