codeforces672D——Robin Hood详解
- Robin Hood
问题描述(google翻译)
我们都知道罗宾汉令人印象深刻的故事。罗宾汉利用他的射箭技巧和他的智慧从富人那里偷钱，然后把它归还给穷人。
在Kekoland有n个公民，每个人都有ci硬币。每天，罗宾汉将从该市最富有的人那里拿出1枚硬币，然后将它交给最贫穷的人（最富有的1枚硬币后最穷的人）。如果选择不是唯一的，他将随机选择其中一个。可悲的是，罗宾汉已经老了，想要在k天退休。他决定在最后几天帮助穷人。
罗宾汉拿走他的钱后，最富有的人也可能成为最穷的人，甚至可能会发生罗宾汉将他的钱还给他的钱。例如，如果所有人拥有相同数量的硬币，那么第二天他们也将拥有相同数量的硬币。
你的任务是找出k天后最富有和最贫穷的人之间的差异。请注意，最富有和最穷的人随意选择不会影响答案。
输入
输入的第一行包含两个整数n和k（1≤n≤500000,0≤k≤109） - Kekoland的公民人数和Robin Hood退休前剩余的天数。
第二行包含n个整数，其中第i个是ci（1≤ci≤109） - 第i个人的初始财富。
- 输出
- 打印一行，包含最富裕和最贫穷人口财富之间的差异。
- 样例输入 1
4 1
1 1 4 2
- 样例输出 1
2
- 样例输入 2
3 1
2 2 2
- 样例输出 2
0
- 问题分析
- 算出这批数据的平均值，将人群分为高于平均水平和低于平均水平的两类
- 二分法找到一个均值，满足低于平均水平并且在 k 天内能补回平均水平的人，k 为控制变量
- 二分法找到一个均值，满足高于平均水平并且在 k 天内能捐出去的人的集合，k 为控制变量
- 两个均值差就是贫富差
#include <iostream> #define Maxn 5000001 using namespace std; typedef long long int LL; LL n; //people
int k; //days
int money;
LL people[Maxn] = {}; int judge(LL day);
int judge1(LL day); int main()
{
ios::sync_with_stdio(false);
LL i = ;
LL sum = ;
cin >> n >> k;
for(; i <= n; i++)
{
cin>>people[i];
sum += people[i];
}
LL limit = sum / n;
LL limit2 = limit;
if(sum % n)
limit2++;
LL l = ;
LL r = limit;
LL mid;
LL result = ,mark = ,mark1 = ;
while(l <= r)
{
mid= (l + r) / ;
if(judge(mid))
{
mark = mid;
l = mid + ;
}
else
{
r = mid - ;
}
}
l = limit2;
r = sum;
while(l <= r)
{
mid = (l + r) / ;
if(judge1(mid))
{
mark1 = mid;
r = mid - ;
}
else
{
l = mid + ;
}
}
result = mark1 - mark;
cout<<result;
return ;
} int judge(LL day)
{
LL res = ;
for(LL j = ;j <= n;j++)
{
if(people[j] < day)
res += day - people[j];
}
return res <= k;
}
int judge1(LL day)
{
LL res = ;
for(LL j = ;j <= n;j++)
{
if(people[j] > day)
res += people[j] - day;
}
return res <= k;
}