2019沈阳网络赛F-Honk`s pool

2019/09/15 14:34
阅读数 20

F-Honk`s pool

题目链接:https://nanti.jisuanke.com/t/41406

题目大意:honk有n个水池,第i个水池中有a【i】升水,每天honk会进行一下操作

1.从水最多的水池中取一升水(如果有多个水最多的池子,任意选择一个)从中取1L

2.找到水最少的一个池子(如果有多个水最少的池子,任意选择一个),把那一升水倒入其中

问你k天之后,水池中水的极差是多少

解题思路:

1.暴力模拟,至于为什么这样能过,我也不知道,肯定是数据水的原因,代码看下

2.二分

在这个操作的过程中,所有水池肯定都会向平均值移动,因此首先要求出平均值ave,在这个n个池子中

水的转移量是一定的也就是k,因此我们先二分出大于ave在这k天中所能转移的最大水量,再二分小于ave的水池

能获得的最大谁量,最终相减即可

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
typedef long long ll;
ll a[maxn];
ll n,k;
bool check(ll mid,bool flag=false)
{
    ll sum=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i]>=mid&&flag==false) sum+=a[i]-mid;
        else if(a[i]<=mid&&flag==true)   sum+=mid-a[i];
    }
    if(sum<=k) return true;
    else return false;
}
int main()
{
std::ios::sync_with_stdio(false);
while(std::cin>>n>>k)
{
ll top,low,sum=0;
for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i];
sort(a+1,a+1+n);
ll maxx=a[n];
ll minn=a[1];
if(sum%n==0)
{
    top=low=sum/n;
}
else
{
    low=sum/n+1;
    top=sum/n;
}
ll ans=0;
ll ls=low,rs=maxx;
while(ls<=rs)
{
    ll mid=(ls+rs)>>1;
    if(check(mid))
    {
        ans=mid;
        rs=mid-1;
    }
    else ls=mid+1;
}
ll ans1=0;
ls=minn,rs=top;
while(ls<=rs)
{
    ll mid=(ls+rs)>>1;
    if(check(mid,true))
    {
        ans1=mid;
        ls=mid+1;
    }
    else rs=mid-1;
}
cout<<ans-ans1<<endl;
}
return 0;
}

 

展开阅读全文
ios
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
OSCHINA
登录后可查看更多优质内容
返回顶部
顶部