题解

new_user_2 2024-03-17 14:56:14

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;
}