P16198 [ROIR 2014 Day 2] Cond 空调 题解
P16198 [ROIR 2014 Day 2] Cond 空调
Link: https://www.luogu.com.cn/problem/P16198
题目描述
在“智慧校园”项目中，决定为学校的每个教室安装一台新一代空调，用于自动制冷和通风。根据设计，每个教室只能装一台空调，且空调的功率必须满足教室的大小——教室越大，空调功率越强。
学校的教室编号从1 11到n nn连续排列。已知编号为i ii的教室需要一台功率至少为a i a_iai瓦特的空调。
学校管理层提供了m mm种不同型号的空调可供采购。每种型号的空调都有对应的功率和价格。请你写个程序，算出给所有教室配备空调所需的最低总花费。
输入格式
第一行包含一个整数n ( 1 ≤ n ≤ 50 000 ) n\ (1 \le n \le 50\,000)n(1≤n≤50000)，表示教室数量。
第二行包含n nn个整数a i ( 1 ≤ a i ≤ 1000 ) a_i\ (1 \le a_i \le 1000)ai(1≤ai≤1000)，表示编号为i ii的教室所需空调的最低功率（瓦特）。
第三行包含一个整数m ( 1 ≤ m ≤ 50 000 ) m\ (1 \le m\le 50\,000)m(1≤m≤50000)，表示可选空调型号数量。
接下来m mm行，每行包含两个整数b j b_jbj和c j ( 1 ≤ b j ≤ 1000 , 1 ≤ c j ≤ 1000 ) c_j\ (1 \le b_j \le 1000, 1 \le c_j \le 1000)cj(1≤bj≤1000,1≤cj≤1000)，分别表示第j jj种空调的功率（瓦特）和价格。
输出格式
输出一个整数，表示给所有教室配备空调的最低总花费。保证至少存在一种方案能满足所有教室的需求。
输入输出样例 #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 10001000元。
第二个样例中，最优方案是给第1 11和第2 22个教室装第4 44种型号的空调，给第3 33个教室装第3 33种型号的空调，总价是13 1313元（3 + 3 + 7 3 + 3 + 73+3+7）。
评分
对于50 5050分的数据，n , m ≤ 1000 n,m\le1000n,m≤1000。
翻译来源：GPT 4.1 mini。
Solution
1. 题意
为教室安装空调，求满足各个教室最小功率需求的总花费。
2. 分析
注意到所有的空调功率皆为1 ∼ 1000 1\sim 10001∼1000范围的整数，因此很容易想到，利用桶思想，统计每种功率的空调的最小花费，一边输入一边更新即可。然后对每个教室，选用一个功率大于需求且花费最低的即可。
注意将桶的元素初始化为无穷大或者− 1 -1−1，以表示不存在这种功率的空调。
3. 代码
usingSystem;classP16198{staticvoidMain(){stringinputData=Console.In.ReadToEnd();string[]tokens=inputData.Split(newchar[]{' ','\n','\r','\t'},StringSplitOptions.RemoveEmptyEntries);intti=0;intn,m;int[]a=newint[50005];int[]d=newint[1005];for(inti=1;i<=1000;++i)d[i]=2147483647;n=int.Parse(tokens[ti++]);for(inti=0;i<n;++i)a[i]=int.Parse(tokens[ti++]);m=int.Parse(tokens[ti++]);while(m-->0){intb,c;b=int.Parse(tokens[ti++]);c=int.Parse(tokens[ti++]);d[b]=Math.Min(d[b],c);}for(inti=999;i>=1;--i)d[i]=Math.Min(d[i],d[i+1]);longans=0;for(inti=0;i<n;++i)ans+=d[a[i]];Output(ans);}staticvoidOutput<Tp>(Tpvalue){Console.Write(value);}}