qduoj 1120 大家一起凑人品(思维+二分上下界)

题意

ACM集训队每个人都有自己的人品值,每一天,人品最好的一个人会给人品最差的一个人分一个点数人品值,问k天后,人品最好和人品最差的两个人的人品值之差是多少。

当人品最好的与人品最差的相差小于等于1时,就不再分配。

思路:

写了一晚上模拟到现在都不知道错在哪了。这个题还是不错的。
两次二分,考虑到加减算是一天,且有加必有减。那么我们就可以先考虑人品多的人k天后人品的一个最大值,在考虑人品少的k天后人品的一个最小值。这就得到了上下界,如果上界<=下界就说明分到了平均值处。

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<bits/stdc++.h>

using namespace std;
const int maxn = 5e5 + 5;
typedef long long ll;
ll a[maxn];
ll n,k;
int check1(ll x)
{
ll res = 0;
for(int i = 1;i <= n;++i)
{
if(a[i] > x) res += a[i] - x;
}
return res <= k;
}
int check2(ll x)
{
ll res = 0;
for(int i = 1;i <= n;++i)
{
if(x > a[i])
res += x - a[i];
}
return res <= k;
}
int main()
{
while(cin >> n >> k)
{
ll mx = 0,sum = 0;
for(int i = 1;i <= n;++i)
scanf("%lld",&a[i]),mx = max(mx,a[i]),sum += a[i];
ll l = 1,r = mx,mid,up,down;
while(l <= r)
{
mid = l + r >> 1;
if(check1(mid)){ up = mid,r = mid - 1;}
else
l = mid + 1;
}
l = 1,r = mx;
while(l <= r)
{
mid = l + r >> 1;
if(check2(mid))
{
down = mid;
l = mid + 1;
}
else
r = mid - 1;
}
if(up <= down)
{
if(sum % n == 0) puts("0");
else puts("1");
}
else{
printf("%lld\n",up - down);
}
}
return 0;
}


-------------本文结束感谢您的阅读-------------


本文标题:qduoj 1120 大家一起凑人品(思维+二分上下界)

文章作者:Statusrank

CSDN博客欢迎来访!

发布时间:2018年09月22日 - 16:09

最后更新:2018年12月20日 - 21:12

原始链接:https://statusrank.xyz/articles/b0b3e006.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

万水千山总是情,就给五毛行不行!

相关文章: