做赚钱的网站,网络营销是什么300字,给网站做认证,跨境电商官网题目题意官方题解#xff1a;百度翻译思路ac代码题意
给出一列数#xff0c;至多n个操作使其中的数1或-1#xff0c;要求得到最小的差值#xff08;最大值-最小值#xff09;#xff1b;
You are given a sequence a1_{1}1,a2_{2}2,…,an_{n}n consisting of nn …
题目题意官方题解百度翻译思路ac代码题意
给出一列数至多n个操作使其中的数1或-1要求得到最小的差值最大值-最小值
You are given a sequence a1_{1}1,a2_{2}2,…,an_{n}n consisting of nn integers.
You may perform the following operation on this sequence: choose any element and either increase or decrease it by one.
Calculate the minimum possible difference between the maximum element and the minimum element in the sequence, if you can perform the aforementioned operation no more than k times.
Input The first line contains two integers n and k (2≤n≤105^{5}5,1≤k≤1014^{14}14)— the number of elements in the sequence and the maximum number of times you can perform the operation, respectively.
The second line contains a sequence of integers a1_{1}1,a2_{2}2,…,an_{n}n(1≤ai≤109^{9}9)
Output Print the minimum possible difference between the maximum element and the minimum element in the sequence, if you can perform the aforementioned operation no more than kk times.
Examples Input 4 5 3 1 7 5 Output 2 Input 3 10 100 100 100 Output 0 Input 10 9 4 5 5 7 5 4 5 2 4 3 Output 1 Note In the first example you can increase the first element twice and decrease the third element twice, so the sequence becomes [3,3,5,5] and the difference between maximum and minimum is 2. You still can perform one operation after that, but it’s useless since you can’t make the answer less than 2.
In the second example all elements are already equal, so you may get 0 as the answer even without applying any operations.
官方题解 百度翻译
假设得到的数组中的最大值应该是R最小值应该是L。让我们估计使用这些属性生成数组所需的操作数。所有小于l的元素都应该增加到l所有大于r的元素都应该减少到r我们不必对剩余的元素执行任何操作。 为什么呢假设我们构造了一个 L∉A 和 R∉A的答案。如果我们增加到L的元素的数量不小于我们减少到R的元素的数量那么我们可以构造最小等于L 1和最大等于R 1的答案并且不需要更多的操作。如果我们增加到LL的元素的数量小于我们减少到R的元素的数量那么我们构造L1的最小值和最大值R 1的答案。所以我们可以移动范围[lr]使它的一个端点属于 现在我们可以解决如下问题在结果数组中迭代最大值找到二进制搜索所能得到的最大最小值然后反求在得到的数组中对最小值进行迭代并用二进制搜索求出最大的最大值。为了检查我们需要多少操作例如要使所有值都不小于ll我们可以通过另一个二进制搜索找到需要更改的元素的数量让这些元素的数量为m并用前缀sums找到它们的和让它们的和为s。然后所需的操作数正好是lm-s。可以使用相同的方法来查找使所有元素不大于r的操作数。 这是问题本来应该解决的方式但不幸的是我们没有找到一个更容易贪婪的解决方案。
思路
就是一道贪心题·但由于操作次数过大范围需定义为 long long分情况到每个数的个数大小从两边向中间推进当两边数相等时结束。感觉题挺简单但测试的时候连题都没看完。一是英语垃圾二还是学的不精
ac代码
#includestdio.h
#includestring.h
#includealgorithm
using namespace std;
const int M1e510;
typedef long long ll;
ll m,n;
ll dp[M],book[M],s[M];
int main()
{scanf(%lld%lld,m,n);for(ll i1; im; i){scanf(%d,dp[i]);book[i]1;}sort(dp,dpm1);ll k1;s[k]dp[1];for(ll i2; im; i){if(s[k]dp[i])book[k];else{k;s[k]dp[i];}}ll a1,bk;while(n){if(s[a]s[b])break;if(book[a]book[b]){ll bbbook[b]*(s[b]-s[b-1]);if(nbb){s[b]s[b]-(n/book[b]);break;}n-bb;book[b-1]book[b];b--;}else{ll aabook[a]*(s[a1]-s[a]);if(naa){s[a]s[a](n/book[a]);break;}n-aa;book[a1]book[a];a;}}printf(%lld\n,s[b]-s[a]);return 0;
}
