CF1471

CF1471-C. Strange Birthday Party

题意：

你要举办一场生日派对。派对有n" role="presentation">n个人，每个人都有一个数字ki" role="presentation">ki。超市有m" role="presentation">m件礼物，购买每件礼物需要花费&#x0024;cj(c1&lt;c2&lt;...&lt;cm)" role="presentation">$cj(c1<c2<...<cm)，且每个礼物只有一件。你要给这n" role="presentation">n个人发东西，对于第i" role="presentation">i个人，你有两种选择：

给第i" role="presentation">i个人发礼物，那么给这个人的礼物要求j&lt;=ki" role="presentation">j<=ki，即礼物的编号不能超过这个人的数字ki" role="presentation">ki;

直接给这个人&#x0024;cki" role="presentation">$cki.

现在要你求出最小的花费。

思路：

按花费从小到大依次分配礼物。假设现在要分配的礼物的编号是cur" role="presentation">cur，利用贪心的思想，当cur&lt;=ki" role="presentation">cur<=ki时，依次将花费最小的礼物分给ki" role="presentation">ki最大的人；当cur&gt;ki" role="presentation">cur>ki时，直接给这位朋友&#x0024;cki" role="presentation">$cki。

原因如下：当cur&lt;=ki" role="presentation">cur<=ki时，有ccur&lt;=cki" role="presentation">ccur<=cki；当cur&gt;ki" role="presentation">cur>ki时，有cki&lt;ccur" role="presentation">cki<ccur，每次都取两者中较小的。

AC代码：

#include <cstdio>#include <cstring>#include <algorithm> typedef long long ll; const int Maxn = 300005; int a[Maxn], b[Maxn]; void solve() {int n, m;scanf("%d %d", &n, &m);for (int i = 1; i <= n; i++) {scanf("%d", a + i);}for (int i = 1; i <= m; i++) {scanf("%d", b + i);}std::sort(a + 1, a + n + 1);ll ans = 0;int cur = 1;for (int i = n; i > 0; i--) {if (a[i] > cur) {ans += b[cur++];} else {ans += b[a[i]];}}printf("%lld\n", ans);} int main() {int T;scanf("%d", &T);while (T--) {solve();}return 0;}

网址：CF1471 https://m.mxgxt.com/news/view/2074300

随便看看