1471C - Strange Birthday Party
05 Jan 2021 — Tags: sorting,greedy — URLAssign people with higher default cost, $k_i$, to the presents with lower cost.
Time complexity: $O(n \log{n})$
Memory complexity: $O(n)$
Click to show code.
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
ll solve(vi k, vi c)
{
sort(begin(k), end(k), greater<int>());
int cur = 0;
ll ans = 0;
for (auto &ki : k)
{
if (cur < ki)
ki = cur++;
ans += c[ki];
}
return ans;
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int t;
cin >> t;
while (t--)
{
int n, m;
cin >> n >> m;
vi k(n), c(m);
for (auto &ki : k)
cin >> ki, ki--;
for (auto &ci : c)
cin >> ci;
cout << solve(k, c) << endl;
}
return 0;
}