题目内容

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

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

题解

题面描述

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

思路

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

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