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

样例输入2

1
2
3

5
11 14 6 13 11
4 68

样例输出2

题解

每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。

代码

#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;
}