蓝桥杯——冒险者公会

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

问题描述

一个地区包含 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
村庄1委托难度值	7	3	\
村庄2委托难度值	5	\	\
村庄3委托难度值	3	2	2
村庄4委托难度值	1	1	1

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

#include <bits/stdc++.h>
#define ll long longusing 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;
}