题解

题面描述

给定一个n排m列的会场，每个座位的编号按排分配。要求将按顺序到场的来宾安排座位，满足身高高的来宾座位号更大。来宾的拥挤指数为走到自己座位前经过的已坐人数。求所有来宾拥挤指数之和的最小值。

思路

这题的思路是：将来宾按身高排序并分组到每一排，利用树状数组动态维护每个排的已坐人数，通过贪心策略为每个来宾选择最右边的可用座位，计算其拥挤指数（即走到座位前经过的已坐人数），最终累加所有来宾的拥挤指数得到最小值。

1. 排序和分组：将来宾按身高排序，并分组到每一排中。

题目内容

现有一个会场拥有$n*m$个座位，对应编号和分布如图所示，第$k$排的座位编号范围为[$m * (k-1) + 1，m*k$]。假设你已经拥有了来宾的身高$h_i$和到场次序，作为主办方你需要保证 来宾们的体验，对于任意来宾$i,j$的身高$h_i<h_j$时需要保证座位编号$s_i<s_j$。

来宾入场时需要统一从每一排左侧走到自己的座位，但走过有人已经坐好的位置时会比较拥挤，来宾感受到的拥挤指数$9$为走到自己座位前路过的其他来宾个数。请问在保证来宾体验的情况下，所有来宾感受到的拥挤 指数之和最小为多少?

输入描述

第一行输入为$n$和$m$表示有$n$排$m$列座位 ($1≤n,m≤300$)

第二行输入为$n *m$个整数表示按顺序到场的来宾的身高$h_i(1≤h_i≤10^9)$

输出描述

输出一个整数表示在保证来宾体验的情况下，所有来宾拥挤指数之和的最小值

样例1

输入

3 1
9 8 10

输出

0

说明

座位分布为$3$排一列，座位安排如下图所示。每排只有一个位置，宾客感受到的拥挤指数总和为$0$

样例2

输入

1 3
10 33 1

输出

1

说明

座位分布为$1$排$3$列，座位安排如下图所示。为了满足来宾的体验，必须座位安排必须按照下图 所示。

身高为$10$的来宾先到，之后身高为$33$的来宾会经过身高为$10$的来宾从而感受到拥挤，最 后升高为$1$的来宾坐在排头不会经过任何人没有感受到拥挤。所以最小的拥挤指数总和为1。

样例3

输入

3 3
3 4 4 1 1 1 1 1 2

输出

4

说明

座位分布为$3$排$3$列，座位安排如下图所示。

第一排:按身高为$1$的来宾的入场顺序从排尾依次入座，不会感受到拥挤。

第二排:两个身高为$1$的来宾按入场先后入座第二列和第一列，感受到的拥挤指数为0。身高为2的来宾入座最晚，会经过前面两个先入场的身高为$1$的来宾，拥挤指数为$2$。

第三排:考虑来宾体验，身高为$3$的来宾只能坐在第一排第一列，并且比两个身高为$4$的来宾先到。两个身高为$4$的来宾按入场先后入座第三列和第二列，他们感受到的拥挤值都是$1$。所以全场来宾的拥挤指数最小总和为$4$。