原题呈现

题目描述#

小信在玩一款卡牌游戏．对方场上有 $n$ 张怪物卡，第 $i$ 张怪物的初始血量为 $h_i$ ．

小信有两种攻击方式：

群攻：使用一次群攻，会让当前所有存活怪物的血量都减少 $1$ ．如果这次减少后存在至少一只怪物血量变为 $0$ 或更小，这些怪物会立刻死亡，并且群攻效果会立刻再次触发一次（再次让所有仍存活怪物血量减少 $1$ ，并且这次额外效果不会消耗群攻次数）．如此反复，只要某一次群攻触发后有怪物死亡，就会继续自动触发下一次群攻；当某一次触发后没有任何怪物死亡时，这张群攻卡牌的效果结束．
普攻：一次普攻可以选择任意一只存活怪物，使其血量减少 $1$ ．

现在有 $q$ 次询问．每次询问只给出一个整数 $k$ ，表示本次询问中小信可以使用 $k$ 次群攻，普攻的使用次数无限制．小信可以以任意顺序穿插使用群攻与普攻，目标是消灭全部怪物，并使总攻击次数最少．

请你对每次询问输出最少需要多少次攻击．

输入格式#

第一行输入一个整数 $n$ ，表示怪物数量．

第二行输入 $n$ 个整数 $h_1 \sim h_n$ ，表示各怪物初始血量．

第三行输入一个整数 $q$ ，表示询问次数．

接下来 $q$ 行，每行输入一个整数 $k$ ，表示每次询问中小信的群攻次数限制．

输出格式#

输出 $q$ 行．每行输出一次询问的答案：在最优策略下最少需要的总攻击次数．

样例#

样例 1#

输入：

1
10
2
1 3 2 2 6 7 2 1 2 10
3
9
4
1
5
2
6
3
7
4
8
5
9
6
10
7
11
8
12
9

输出：

样例 2#

输入：

输出：

数据范围#

本题采用捆绑评测，对于一个子任务，你必须通过其中的所有数据才能得到相应分数．

子任务编号	分数	$n,q$	特殊性质
1	20	$\le 10$	无
2	10	$\le 5000$	$h_i = n$
3	20	$\le 5000$	无
4	10	$\le 3\times 10^5$	$h_i = n$
5	10	$\le 3\times 10^5$	$q=10$
6	15	$\le 3\times 10^5$	无
7	15	$10^6$	无

对于所有数据： $1 \le n,q \le 10^6$ ， $1 \le h_i,k \le n$ ．

结论题，结论为：由于值域很小，我们可以将所有数字按值放在一个桶中，桶中所有为 0 的且后面存在非 0 位置的位置视为一个空格．每一次群攻可以消灭一个空格，当场上没有剩余空格时，再进行一次群攻即可消灭全部敌人．

由于群攻总是比普攻不劣，我们先考虑群攻次数足够的情况，此时只需要施展场上空格次数 +1 次群攻即可．

群攻次数不足时呢？我们考虑使用普攻填空格．从后面往前进行遍历，每当遇到一个空格 $i$ ：

若该格右边存在：同种血量的怪物存在多种，则选择血量最接近的一种，该种怪物中的一个通过普攻降到血量 $i$ ，来填补这个空格的同时，又不会拆东墙补西墙．
否则，选择当前血量最大的怪兽，通过普攻将其血量变为 $i$ ，用来填补这个空格．

例如：现在存在 $2,3,5,7,7,9$ ，将其整理成桶的形式： $1_0,2_1,3_1,4_0,5_1,6_0,7_2,8_0,9_1$ ，所有不存在（即为空格）的数值为 $1,4,6,8$ ．

从右边开始：

对于 $8$ ，让 $9$ 通过一次普攻变成 $8$ ．此时： $2,3,5,7,7,8$ ．代价为 1．
对于 $6$ ，让 $7$ 通过一次普攻变成 $6$ ．此时： $2,3,5,6,7,8$ ．代价为 1．
对于 $4$ ，让 $8$ 通过四次普攻变成 $4$ ．此时： $2,3,4,5,6,7$ ．代价为 4．
对于 $1$ ，让 $7$ 通过六次普攻变成 $1$ ．此时： $1,2,3,4,5,6$ ．代价为 6．

显然，由于存在群攻，这四次填空格的方式并不需要全部操作．只需要贪心的选择其中的部分空格填上，即选择代价最少的几种．因此：将 4 次操作按照代价从小到大排序，在其中选择 $4-k+1$ 项（其中 $k$ 是允许群攻的次数），所需代价就是普攻的次数，再加上 $k$ 次群攻即可．

标程

1
#include <bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
const int N = 1e6 + 100;
5
int n, h[N], q, a[N];
6
ll sum[N];
7

8
signed main() {
9
#ifdef ONLINE_JUDGE
10
    freopen("profane.in", "r", stdin);
11
    freopen("profane.out", "w", stdout);
12
#endif
13
    ios::sync_with_stdio(false);
14
    cin.tie(0);
15
    cout.tie(0);
16
    cin >> n;
17
    for (int i = 1; i <= n; i++) {
18
        cin >> h[i];
19
    }
20
    sort(h + 1, h + n + 1);
21
    stack<int> stk;
22
    vector<int> vec;
23
    int maxh = -1;
24
    for (int i = 1; i <= n; i++) {
25
        a[h[i]]++;
26
        maxh = max(maxh, h[i]);
27
    }
28
    for (int i = maxh; i >= 1; i--) {
29
        if (a[i] > 1) {
30
            for (int j = 2; j <= a[i]; j++)
31
                stk.push(i);
32
        } else if (a[i] == 0) {
33
            int cost = 0;
34
            if (!stk.empty()) {
35
                int tp = stk.top();
36
                stk.pop();
37
                cost = tp - i;
38
            } else {
39
                cost = maxh - i;
40
                maxh--;
41
            }
42
            vec.push_back(cost);
43
        }
44
    }
45
    sort(vec.begin(), vec.end());
46
    for (int i = 0; i < vec.size(); i++) {
47
        sum[i + 1] = sum[i] + vec[i];
48
    }
49
    cin >> q;
50
    while (q--) {
51
        int k;
52
        cin >> k;
53
        if (k > vec.size()) {
54
            cout << vec.size() + 1 << endl;
55
        } else {
56
            int need = vec.size() - k + 1;
57
            cout << sum[need] + k << endl;
58
        }
59
    }
60
    return 0;
61
}

音乐

音乐

题目描述#

输入格式#

输出格式#

样例#

样例 1#

样例 2#

数据范围#

文章分享

音乐

安吉D6-T3

题目描述#

输入格式#

输出格式#

样例#

样例 1#

样例 2#

数据范围#

文章分享