題目

• 題意
• 官方題解：
• 百度翻譯
• 思路
• ac代碼

題意

給出一列數，至多n個操作使其中的數+1或-1，要求得到最小的差值（最大值-最小值）；

You are given a sequence a${}_1$,a${}_2$,…,a${}_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≤10${}^5$,1≤k≤10${}^{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 a${}_1$,a${}_2$,…,a${}_n$(1≤ai≤10${}^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的元素的數量，那么我們構造L+1的最小值和最大值R+ 1的答案。所以我們可以移動范圍[l，r]，使它的一個端點屬于
現在我們可以解決如下問題：在結果數組中迭代最大值，找到二進制搜索所能得到的最大最小值，然后反求：在得到的數組中對最小值進行迭代，并用二進制搜索求出最大的最大值。為了檢查我們需要多少操作，例如，要使所有值都不小于ll，我們可以通過另一個二進制搜索找到需要更改的元素的數量（讓這些元素的數量為m），并用前綴sums找到它們的和（讓它們的和為s）。然后，所需的操作數正好是lm-s。可以使用相同的方法來查找使所有元素不大于r的操作數。
這是問題本來應該解決的方式，但不幸的是，我們沒有找到一個更容易貪婪的解決方案。

思路

就是一道貪心題·，但由于操作次數過大，范圍需定義為 long long分情況（到每個數的個數大小）從兩邊向中間推進，當兩邊數相等時結束。（感覺題挺簡單，但測試的時候，連題都沒看完。一是英語垃圾，二還是學的不精 ）

ac代碼

#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; const int M=1e5+10; typedef long long ll; ll m,n; ll dp[M],book[M],s[M]; int main() {scanf("%lld%lld",&m,&n);for(ll i=1; i<=m; i++){scanf("%d",&dp[i]);book[i]=1;}sort(dp,dp+m+1);ll k=1;s[k]=dp[1];for(ll i=2; i<=m; i++){if(s[k]==dp[i])book[k]++;else{k++;s[k]=dp[i];}}ll a=1,b=k;while(n){if(s[a]==s[b])break;if(book[a]>book[b]){ll bb=book[b]*(s[b]-s[b-1]);if(n<=bb){s[b]=s[b]-(n/book[b]);break;}n-=bb;book[b-1]+=book[b];b--;}else{ll aa=book[a]*(s[a+1]-s[a]);if(n<=aa){s[a]=s[a]+(n/book[a]);break;}n-=aa;book[a+1]+=book[a];a++;}}printf("%lld\n",s[b]-s[a]);return 0; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的Minimizing Difference CodeForces - 1244E(贪心题)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。