B.youngmagician想要检查角色练度 困难题，核心思路为：求出n个数组各选一个数之和的第k小。易知应该采取最弱对最弱的方法，即最弱的角色应该去对最弱的组合进行试炼。 首先先将输入的数排序，假设n=4的情况下,毫无疑问，最弱的组合就是各个数组各自选择最弱的数的组合，记为(1,1,1,1),在那之后考虑次弱的组合，易知次弱的组合一定是某个数组中的第二弱的数替换了第一弱的数，即（2，1，1，1），（1，2，1，1），（1，1，2，1），（1，1，1，2）中的一个，使用优先队列维护数组的若干和以及他们是第几个数。每次从优先队列头顶取出一个元素后，再次加入n个数，例如，假如取出（1，2，1，1），则再次向优先队列中加入（2，2，1，1），（1，3，1，1），（1，2，2，1），（1，2，1，2）。重复k次即可，时间复杂度O(nklog(nk)+nmlogm)，空间复杂度O(n^2*k)。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
struct op {
ll sum;
vector<ll> t;
friend bool operator<(op l, op r) { return l.sum > r.sum; }
};
void solve() {
// freopen("8.in", "r", stdin);
// freopen("8.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
ll n, m, k;
cin >> k;
vector<ll> ch(k);
for (ll x = 0; x < k; x++) {
cin >> ch[x];
}
sort(ch.begin(), ch.end());
cin >> n >> m;
vector<ll> a[n];
for (ll x = 0; x < n; x++) {
for (ll y = 1; y <= m; y++) {
ll temp;
cin >> temp;
a[x].push_back(temp);
}
sort(a[x].begin(), a[x].end());
}
map<vector<ll>, ll> mp;
priority_queue<op> z;
op st;
st.sum = 0;
for (ll x = 0; x < n; x++) {
st.sum += a[x][0];
st.t.push_back(0);
}
z.push(st);
ll ans = 0;
for (int cnt = 0; cnt < k; cnt++) {
ll i = ch[cnt];
op temp = z.top();
if (mp[temp.t]) {
z.pop();
cnt--;
continue;
}
// cout<<temp.sum<<" "<<i<<" \n";
if (i < temp.sum) {
continue;
} else {
ans++;
mp[temp.t] = 1;
z.pop();
ll val = temp.sum;
for (ll j = 0; j < n; j++) {
op newop;
ll b = temp.t[j];
if (b + 1 == m)
continue;
newop.sum = val - a[j][b] + a[j][b + 1];
newop.t = temp.t;
newop.t[j] = b + 1;
z.push(newop);
}
}
}
cout << ans << "\n";
return;
}
int main() {
solve();
return 0;
}