G3022 [GESP202512 三级] 小杨的智慧购物 题解

知识点：一维数组、分组最值、累加。

解题思路

每种商品保存当前最低报价，逐条报价更新对应类别最小值，最后把全部类别的最低价相加。

为什么正确

每一类独立选择且只需一件，各类局部最低价同时可取，因此其和为全局最低成本。

易错点

同一类报价应取最小，不能覆盖成最后一条报价；总和用long long。

复杂度

时间O(m+n)，空间O(m)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m,n,k,p;
    cin>>m>>n;
    vector<int>a(m+1,1001);
    while(n--) {
        cin>>k>>p;
        a[k]=min(a[k],p);
    }
    cout<<accumulate(a.begin()+1,a.end(),0LL);
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用6个自行生成的测试点。