Sol
首先 \(c\) 不能变,否则第一列就会改变。
然后注意到 \(i,j(i<j)\) 能交换当且仅当满足以下任意一条:
- \(\displaystyle\max_{k=i+1}^{j-1}a_k<\min(a_i,a_j)\)
- i+1=j
那么考虑从小到大做,每次把小的数删除,然后维护相邻同色数组成的连通块,每一轮一定能从同色连通块中选出一个数作为当前的方案,然后将大小减一。
Code
Link。
首先 \(c\) 不能变,否则第一列就会改变。
然后注意到 \(i,j(i<j)\) 能交换当且仅当满足以下任意一条:
那么考虑从小到大做,每次把小的数删除,然后维护相邻同色数组成的连通块,每一轮一定能从同色连通块中选出一个数作为当前的方案,然后将大小减一。
Link。