蓝桥杯——冒险者公会

学校快期末考试了，把以前做过的题目都拿出来整理一下！以免丢失！！

问题描述

一个地区包含 n 个村庄，每个村庄发布了一些委托任务，需要冒险者的帮助。

冒险者公会共有 m 位冒险者。某位冒险者具有能力值 xi​，这表示他能够完成难度值小于等于 x 的委托任务。每位冒险者最多只能出击一轮，在这一轮中，他们可以不重复地通过若干个村庄。

当一名冒险者路过一个村庄时，他最多只能完成该村庄的一个委托任务，且这个委托的难度不能超过冒险者的能力值。冒险者也可以选择在路过一些村庄时不完成任何委托任务。同样的，每个委托任务只需要被完成一次。

无论冒险者完成多少任务，这名冒险者出击一轮的代价都等同于冒险者的能力值。

现在的目标是确定一种冒险者的出勤方案，以使得完成所有村庄的委托任务的总代价最小。

输入格式

第一行输入两个整数 m 和 n ，分别表示冒险者的数量和村庄的数量，0<m,n≤103。

第二行 m 个整数 x1,x2,...xi,...xm，代表每位冒险者的能力值，0<xi≤103。

接下来 n 行，每行代表一个村庄，每行第一个整数 k 表示该村庄的委托数量，此后 k 个不大于 103 的正整数表示该村庄的每个委托任务的难度值，0<k≤103。

输出格式

在一行中输出一个整数，表示完成所有委托所需的最小总代价。如果不能完成所有的委托，则直接输出 −1。

样例输入

3 4
2 9 6
2 3 7
1 5
3 2 2 3
3 1 1 1

样例输出

17

样例说明

一种可行的代价最小的执行方案如下。

将三轮任务的代价求和 9+6+2 得到答案 17。

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int main() {
    int m, n;
    cin >> m >> n;  // 输入冒险者数量和村庄数量
    vector<int> level(m);
    for (int i = 0; i < m; i++)
        cin >> level[i];  // 输入冒险者能力值
    sort(level.begin(), level.end());  // 按从小到大排序
    vector<vector<int> > city(n, vector<int>(m, 0));
    int k;
    for (int i = 0; i < n; i++) {
        cin >> k;  // 输入委托个数
        if (k > m) {  // 如果委托比冒险者人数还多，那么一定不能完成
            cout << -1 << endl;
            return 0;
        }
        for (int j = 0; j < k; j++)
            cin >> city[i][j];  // 输入每个委托难度值
        sort(city[i].begin(), city[i].end());  // 按从小到大排序
    }
    vector<int> mx(m);
    int unit;
    for (int i = 0; i < m; i++) {  // 每一轮都完成每个村里最难的一个任务，记录每一轮的最难任务的代价
        unit = city[0][i];
        for (int j = 0; j < n; j++)
            if (unit < city[j][i])
                unit = city[j][i];
        mx[i] = unit;
    }
    int mani = 0, cityi = 0;
    ll ans = 0;
    while(cityi < m && mx[cityi] == 0)
        cityi++;
    while (mani < m && cityi < m) {  // 双指针查看是否能够完成所有委托
        if (mx[cityi] <= level[mani]) {
            cityi++;
            ans += level[mani];
        }
        mani++;
    }
    if (cityi == m)  // 如果完成所有委托则输出总代价
        cout << ans << endl;
    else  // 如果所有冒险者都已派遣但仍有委托没有完成则失败
        cout << -1;

    return 0;
}