2018计蒜之道初赛第一场A题百度无人车

百度无人车

百度一共制造了 n 辆无人车,其中第 ii 辆车的重量为 a_i\ \mathrm{kg}ai kg。

由于车辆过重会增大轮胎的磨损程度,现在要给这 n 辆车减轻重量。每将一辆车减轻 1\ \mathrm{kg}1 kg需要消耗 p 万百度币,总预算为 s 万百度币。

现在希望你设计一种最优的减重方案,使得最重的车辆的重量是所有减重方案中最小的。任何时候,每辆车的重量必须大于等于 1\ \mathrm{kg}1 kg。并且减重方案只能减轻整数 \mathrm{kg}kg。

输入格式

第一行输入一个整数 n,表示百度无人车的数量。

接下来一行输入 n 个整数,其中第 ii 个整数 a_iai表示第 ii 辆车的重量。

接着一行输入两个整数 p,s,分别表示把一辆车减重 1\ \mathrm{kg}1 kg 需要花费 p 万百度币,总的预算是 s 万百度币。

保证 1 \le n \le 200001≤n≤20000,1 \le a_i \le 200001≤ai≤20000,1 \le p \le 200001≤p≤20000,1 \le s \le 10^{18}1≤s≤1018。

输出格式

输出一个整数,表示经过你设计的最优减重方案后,最重的车辆的重量是多少 \mathrm{kg}kg。

样例输入1

1
2
3
4
6 7 8 9
1 3

样例输出1

1
7

样例输入2

1
2
3
5
11 14 6 13 11
4 68

样例输出2

1
8

题解

每1kg消耗p元,一共s元,因此一共可以减s/p(kg),直接s=s/p就行了。先对整个数组进行排序,然后再进行操作。一开始用二分,时间复杂度Onlogn,通不过,因此换了一种线性的方法,时间复杂度On。首先建一个差分数组,储存该元素和前一个元素的差值。以1, 2, 4, 6, 9为例,差分数组为1,1,2,2,3。然后从后往前操作。假设s=s/p之后s为10,首先s与第n个元素差分数组比较,如果大,则s-3=7。再和第n-1比较,由于该位置后面还有一个元素,因此若要改变该元素使最大值变小,需同时改变这两个数,后面以此类推三个四个数等等。s和b[n-1]2即2 2比较,大,则s=7-22=3。再和b[n-2] 3比较。比它小,则证明最大部分再该部分。b[n-2]=b[n-2]-s/3即1,结束循环。现在的差分数组为1,1,1,0,0,现在依次从从b[1]加到b[n就好了,即3。另外由于最小值为1,因此需要对第一个元素特判一下,如果小于1需改为1。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 200007;
typedef long long ll;
int a[maxn], b[maxn];
ll p, s, n;
int main() {
cin >> n;
a[0] = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; i++) {
b[i] = a[i] - a[i - 1];
}
cin >> p >> s;
s /= p;
ll ans = 0;
for (int i = n; i>0; i--) {
if (s >= b[i] * (n - i + 1)) {
s -= b[i] * (n - i + 1);
b[i] = 0;
}
else {
b[i] -= s / (n - i + 1);
for (int j = 2; j <= i; j++)
ans += b[j];
break;
}
if (i == 1 && b[i] <= 1)
break;
}
if (b[1] <= 1)
b[1] = 1;
ans += b[1];
cout << ans << endl;
return 0;
}

纸短情长啊文章结束了但我们的故事还在继续
坚持原创技术分享,您的支持将鼓励我继续创作!