T1

题目描述

杰夫非常喜欢种草，他自己有一片草地，为了方便起见，我们把这片草地看成一行从左到右，并且第$i$个位置的草的高度是$h_i$。杰夫在商店中购买了$m$瓶魔法药剂，每瓶魔法药剂可以让一株草长高$x$，杰夫希望每次都能针对性的使用药剂，也就是让当前长得最矮的小草尽量高，现在杰夫想请你告诉他在使用了$m$瓶魔法药剂之后，最矮的小草在这种情况下最高能到多少。

输入描述

第一行三个整数$n，m，x$分别表示小草的个数，魔法药剂的个数以及每瓶魔法药剂让小草长高的高度。（$1 \leq n, m, x \leq 1e^5$）
第二行$n$个整数分别表示第$i$小草的高度$a_i$。（$1 \leq a_i \leq 1e^9$）

输出描述

使用了$m$瓶药剂之后最矮的小草的最高高度。

示例1

样例输入

3 1 1
1 2 3

样例输出

2

算法

(堆) $O(n + mlog(n))$

C++ 代码

#include <bits/stdc++.h>
using namespace std;

int n, m, x;

int main() {
    cin >> n >> m >> x;

    priority_queue<int, vector<int>, greater<int>> q;

    while (n -- ) {
        int a; cin >> a; q.push(a);
    }

    for (int i = 0; i < m; i ++ ) {
        int t = q.top(); q.pop();
        q.push(t + x);
    }

    cout << q.top();

    return 0;
}

T2

题目描述

你购买了一个机器人，它现在剩下$C$单位电量，你现在想让它做一些动作愉悦自己。它可以做$n$种动作，每种动作最多做一次，因为你觉得让机器人重复做一种动作是无聊的。每种动作都有一个固定电量花费$c_i$单位电量，以及这个动作的愉悦度$w_i$。请在你电量范围内让它做出让你最愉悦的动作。即做的动作的总电量消耗不能超过$C$，并使愉悦度之和最大。（我们将情景简化，电量在开始动作前就要扣除，若电量不足则无法开始作，不存在动作进行到一半的状态）

输入描述

第一行两个以空格隔开的正整数$n$和$C$，表示动作数量和机器人剩余电量。
接下来$n$行，每行两个以空格隔开的浮点数$c_i$和整数$w_i$，代表第$i$种动作电量消耗以及愉悦
度。
$n \leq 300$
$C \leq 30000$
$0 \leq c_i \leq 900000.0$
$0 < w_i \leq 250$

输出描述

一个整数，表示愉悦度之和的最大值

示例1

样例输入

3 15
5.00 16
9.00 1
8.00 15

样例输出

31

算法

(01背包) $O(m \times n)$

浮点数情况电量放大100倍

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N = 3e6 + 10;

int n, m;
double v;
int f[N], w;

int main() {
    cin >> n >> m;

    for (int i = 0; i < n; i ++ ) {
        cin >> v >> w;
        for (int j = m * 100; j >= (int)(v * 100); j -- )
            f[j] = max(f[j], f[j - (int)(v * 100)] + w);
    }

    cout << f[m * 100];

    return 0;
}

T3

题目描述

我们希望一个序列中的元素是各不相同的，但是理想和现实往往是有差距的。现在给出一个序列$A$，其中难免有些相同的元素，现在提供了一种变化方式，使得经过若干次操作后一定可以得到一个元素各不相同的序列。这个操作是这样的，令$x$为序列中最小的有重复的数字，你需要删除序列左数第一个$x$，并把第二个$x$替换为$2*x$。请你输出最终的序列。例如原序列是[2, 2, 1, 1, 1]，一次变换后变为[2, 2, 2, 1]，两次变换后变为[4, 2, 1]，变换结束

输入描述

输入第一行包含一个正整数$n$，表示序列的长度为$n$。（$1 \leq n \leq 5000$)
第二行有$n$个整数，初始序列中的元素。（$1 \leq a_i \leq 10^8$）

输出描述

输出包含若干个整数，即最终变换之后的结果。

示例1

样例输入

5
5 5 5 5 4

样例输出

20 4

算法

() $O()$

C++ 代码