题解

题面描述

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

思路

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

1. 排序和分组：将来宾按身高排序，并分组到每一排中。
2. 树状数组维护：使用树状数组（Fenwick Tree）动态维护每个排的已坐人数，计算拥挤指数。
3. 贪心策略：每次为当前来宾选择可用的最右边座位，以减少后续来宾的拥挤指数。
4. 动态更新：在每一排中，按身高分组处理，更新树状数组并计算拥挤指数。

代码分析

• 初始化：将来宾按身高排序，并分组到每一排中。
• 树状数组：使用树状数组维护每个排的已坐人数，支持快速查询和更新。
• 计算拥挤指数：对于每一排，按身高分组处理，计算每个来宾的拥挤指数并累加。

问题本质

该问题本质上是动态维护一个有序序列，保证序列的单调性，并在每次插入时选择最优位置以最小化后续操作的代价。

cpp

#include <bits/stdc++.h>
using namespace std;

// 计算 lowbit，用于树状数组
int lowbit(int x) {
    return x & (-x);
}

// 树状数组类
class Fenwick {
public:
    vector<int> dat; // 树状数组的数据存储
    vector<int> tim; // 时间戳，用于清空数组
    int now;         // 当前时间戳

    // 构造函数，初始化树状数组
    Fenwick(int n) : dat(n + 1, 0), tim(n + 1, -1), now(0) {}

    // 查询前缀和
    int query(int x) {
        int res = 0;
        while (x) {
            if (tim[x] == now) { // 只统计当前时间戳的数据
                res += dat[x];
            }
            x -= lowbit(x); // 移动到前一个区间
        }
        return res;
    }

    // 更新树状数组
    void update(int x) {
        while (x < dat.size()) {
            if (tim[x] != now) { // 如果时间戳不一致，清空当前节点
                tim[x] = now;
                dat[x] = 0;
            }
            dat[x] += 1; // 更新当前节点
            x += lowbit(x); // 移动到下一个区间
        }
    }

    // 清空树状数组（通过增加时间戳）
    void clear() {
        now += 1;
    }
};

int main() {
    int n, m;
    cin >> n >> m; // 输入 n 和 m
    vector<int> a(n * m);
    for (int i = 0; i < n * m; ++i) {
        cin >> a[i]; // 输入每个来宾的身高
    }

    // 将身高和索引绑定，方便排序
    vector<pair<int, int>> b;
    for (int i = 0; i < n * m; ++i) {
        b.emplace_back(a[i], i);
    }
    sort(b.begin(), b.end()); // 按身高排序

    // 将排序后的来宾分组到每一排
    vector<vector<pair<int, int>>> c(n);
    for (int i = 0; i < n * m; ++i) {
        c[i / m].push_back(b[i]);
    }

    Fenwick f(n * m); // 初始化树状数组
    int total = 0;    // 总拥挤指数
    for (int i = 0; i < n; ++i) {
        f.clear(); // 清空树状数组
        int j = 0;
        while (j < c[i].size()) {
            int s = j;
            // 处理身高相同的来宾
            while (j < c[i].size() && c[i][j].first == c[i][s].first) {
                // 查询当前来宾的拥挤指数
                total += f.query(c[i][j].second + 1);
                ++j;
            }
            // 更新树状数组
            while (s < j) {
                f.update(c[i][s].second + 1);
                ++s;
            }
        }
    }

    cout << total << endl; // 输出总拥挤指数
    return 0;
}

python

def lowbit(x):
    return x & (-x)  # 计算 lowbit

class Fenwick:
    def __init__(self, n):
        self.dat = [0] * (n + 1)  # 树状数组数据存储
        self.tim = [-1] * (n + 1)  # 时间戳，用于清空数组
        self.now = 0               # 当前时间戳

    def query(self, x):
        res = 0
        while x:
            if self.tim[x] == self.now:  # 只统计当前时间戳的数据
                res += self.dat[x]
            x -= lowbit(x)  # 移动到前一个区间
        return res

    def update(self, x):
        while x < len(self.dat):
            if self.tim[x] != self.now:  # 如果时间戳不一致，清空当前节点
                self.tim[x] = self.now
                self.dat[x] = 0
            self.dat[x] += 1  # 更新当前节点
            x += lowbit(x)   # 移动到下一个区间

    def clear(self):
        self.now += 1  # 清空树状数组（通过增加时间戳）

n, m = map(int, input().split())  # 输入 n 和 m
a = list(map(int, input().split()))  # 输入每个来宾的身高

# 将身高和索引绑定，方便排序
b = []
for i in range(len(a)):
    b.append((a[i], i))
b.sort()  # 按身高排序

# 将排序后的来宾分组到每一排
c = [[] for _ in range(n)]
for i in range(len(b)):
    c[i // m].append(b[i])

f = Fenwick(n * m)  # 初始化树状数组
total = 0           # 总拥挤指数
for i in range(n):
    f.clear()  # 清空树状数组
    j = 0
    while j < len(c[i]):
        s = j
        # 处理身高相同的来宾
        while j < len(c[i]) and c[i][j][0] == c[i][s][0]:
            # 查询当前来宾的拥挤指数
            total += f.query(c[i][j][1] + 1)
            j += 1
        # 更新树状数组
        while s < j:
            f.update(c[i][s][1] + 1)
            s += 1
print(total)  # 输出总拥挤指数

java

import java.util.*;

public class Main {
    static int lowbit(int x) {
        return x & (-x);  // 计算 lowbit
    }

    static class Fenwick {
        int[] dat;  // 树状数组数据存储
        int[] tim;  // 时间戳，用于清空数组
        int now;    // 当前时间戳

        Fenwick(int n) {
            dat = new int[n + 1];
            tim = new int[n + 1];
            Arrays.fill(tim, -1);  // 初始化时间戳
            now = 0;
        }

        int query(int x) {
            int res = 0;
            while (x > 0) {
                if (tim[x] == now) {  // 只统计当前时间戳的数据
                    res += dat[x];
                }
                x -= lowbit(x);  // 移动到前一个区间
            }
            return res;
        }

        void update(int x) {
            while (x < dat.length) {
                if (tim[x] != now) {  // 如果时间戳不一致，清空当前节点
                    tim[x] = now;
                    dat[x] = 0;
                }
                dat[x] += 1;  // 更新当前节点
                x += lowbit(x);  // 移动到下一个区间
            }
        }

        void clear() {
            now += 1;  // 清空树状数组（通过增加时间戳）
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();  // 输入 n
        int m = sc.nextInt();  // 输入 m
        int[] a = new int[n * m];
        for (int i = 0; i < n * m; i++) {
            a[i] = sc.nextInt();  // 输入每个来宾的身高
        }

        // 将身高和索引绑定，方便排序
        List<int[]> b = new ArrayList<>();
        for (int i = 0; i < n * m; i++) {
            b.add(new int[]{a[i], i});
        }
        b.sort((x, y) -> Integer.compare(x[0], y[0]));  // 按身高排序

        // 将排序后的来宾分组到每一排
        List<List<int[]>> c = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            c.add(new ArrayList<>());
        }
        for (int i = 0; i < n * m; i++) {
            c.get(i / m).add(b.get(i));
        }

        Fenwick f = new Fenwick(n * m);  // 初始化树状数组
        int total = 0;                   // 总拥挤指数
        for (int i = 0; i < n; i++) {
            f.clear();  // 清空树状数组
            int j = 0;
            while (j < c.get(i).size()) {
                int s = j;
                // 处理身高相同的来宾
                while (j < c.get(i).size() && c.get(i).get(j)[0] == c.get(i).get(s)[0]) {
                    // 查询当前来宾的拥挤指数
                    total += f.query(c.get(i).get(j)[1] + 1);
                    j++;
                }
                // 更新树状数组
                while (s < j) {
                    f.update(c.get(i).get(s)[1] + 1);
                    s++;
                }
            }
        }
        System.out.println(total);  // 输出总拥挤指数
    }
}

题目内容

现有一个会场拥有$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$。