题目链接
Honk’s-pool(思维)
题目描述
给出一个数组，每次给最小的加一，最大的减一，执行k此，问最后的数组最大值与最小值的差。
思路
这道题有些坑点，但是其实很简单，就是先找出数组中最小值最大化，在找出最大值最小化，然后记得判断这个数组能否变成全为一个数字的情况。
例如1 2 2 3这样的。用二分来判断就可以。然后如果sum%n==0的话，并且最小值大于等于最大值，那么答案就是0，否则答案就是1.
如果最小值小于最大值，答案就是他们之间的差值。
代码实现
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
65
66
67
68
69
70
71
72
73
74
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 5e5+10;
int a[maxn];
int n,k;
bool judge(int x)
{
long long num = 0;
for(int i=0;i<n;i++)
{
if(x-a[i]>0)num+=(x-a[i]);
}
return num<=k;
}
bool judge1(int x)
{
long long num = 0;
for(int i=0;i<n;i++)
{
if(a[i]-x>0)num+=(a[i]-x);
}
return num<=k;
}
int main()
{
while(scanf("%d %d",&n,&k)!=EOF)
{
long long sum = 0 ;
int l = 1e9+7;
int r = 0;
bool ok =false;
for(int i=0;i<n;i++)scanf("%d",&a[i]);
for(int i=0;i<n;i++)
{
if(i!=0)
{
if(a[i]!=a[i-1])
{
ok = true;
}
}
l=min(l,a[i]);
r=max(r,a[i]);
sum+=a[i];
}
if(!ok||n==1)
{
printf("0\n");
continue;
}
int ls = l;
int rr = r;
int ans = l;
while(ls<=rr)
{
int mid = (ls+rr)>>1;
if(judge(mid))ans=mid,ls=mid+1;
else rr=mid-1;
}
ls =l;
rr =r;
int ans1 = r;
while(ls<=rr)
{
int mid = (ls+rr)>>1;
if(judge1(mid))ans1=mid,rr=mid-1;
else ls=mid+1;
}
if(ans1<=ans&&sum%n==0)printf("0\n");
else if(ans1<=ans&&sum%n!=0)printf("1\n");
else printf("%d\n",ans1-ans);
}
}
|