P16198 [ROIR 2014 Day 2] Cond 空调

Link: https://www.luogu.com.cn/problem/P16198

题目描述

在“智慧校园”项目中，决定为学校的每个教室安装一台新一代空调，用于自动制冷和通风。根据设计，每个教室只能装一台空调，且空调的功率必须满足教室的大小——教室越大，空调功率越强。

学校的教室编号从 $1$ 到 $n$ 连续排列。已知编号为 $i$ 的教室需要一台功率至少为 $a_i$ 瓦特的空调。

学校管理层提供了 $m$ 种不同型号的空调可供采购。每种型号的空调都有对应的功率和价格。请你写个程序，算出给所有教室配备空调所需的最低总花费。

输入格式

第一行包含一个整数 $n(1\le n\le 50000)$，表示教室数量。

第二行包含 $n$ 个整数 $a_i(1\le a_i\le 1000)$，表示编号为 $i$ 的教室所需空调的最低功率（瓦特）。

第三行包含一个整数 $m(1\le m\le 50000)$，表示可选空调型号数量。

接下来 $m$ 行，每行包含两个整数 $b_j$ 和 $c_j(1\le b_j\le 1000,1\le c_j\le 1000)$，分别表示第 $j$ 种空调的功率（瓦特）和价格。

输出格式

输出一个整数，表示给所有教室配备空调的最低总花费。保证至少存在一种方案能满足所有教室的需求。

输入输出样例 #1

输入 #1

1
800
1
800 1000

输出 #1

1000

输入输出样例 #2

输入 #2

3
1 2 3
4
1 10
1 5
10 7
2 3

输出 #2

13

说明/提示

第一个样例中，只能买唯一一台空调，价格是 $1000$ 元。

第二个样例中，最优方案是给第 $1$ 和第 $2$ 个教室装第 $4$ 种型号的空调，给第 $3$ 个教室装第 $3$ 种型号的空调，总价是 $13$ 元（$3+3+7$）。

评分

对于 $50$ 分的数据，$n,m\le 1000$。

翻译来源：GPT 4.1 mini。

---

Solution

1. 题意

为教室安装空调，求满足各个教室最小功率需求的总花费。

2. 分析

注意到所有的空调功率皆为 $1\sim 1000$ 范围的整数，因此很容易想到，利用桶思想，统计每种功率的空调的最小花费，一边输入一边更新即可。然后对每个教室，选用一个功率大于需求且花费最低的即可。

注意将桶的元素初始化为无穷大或者 $-1$，以表示不存在这种功率的空调。

3. 代码

using System;

class P16198
{
    static void Main()
    {
        string inputData = Console.In.ReadToEnd();
        string[] tokens = inputData.Split(new char[] { ' ', '\n', '\r', '\t' }, StringSplitOptions.RemoveEmptyEntries);
        int ti = 0;

        int n, m;
        int[] a = new int[50005];
        int[] d = new int[1005];
        for (int i = 1; i <= 1000; ++i) d[i] = 2147483647;
        
        n = int.Parse(tokens[ti++]);
        for (int i = 0; i < n; ++i) a[i] = int.Parse(tokens[ti++]);

        m = int.Parse(tokens[ti++]);
        while (m-- > 0)
        {
            int b, c; 
            b = int.Parse(tokens[ti++]);
            c = int.Parse(tokens[ti++]);
            d[b] = Math.Min(d[b], c);
        }

        for (int i = 999; i >= 1; --i)
            d[i] = Math.Min(d[i], d[i+1]);

        long ans = 0;
        for (int i = 0; i < n; ++i) ans += d[a[i]];
        Output(ans);
    }

    static void Output<Tp>(Tp value)
    {
        Console.Write(value);
    }
}