bzoj 1816: [Cqoi2010]扑克牌

 #include<cstdio>
#include<iostream>
using namespace std;
int l,r,m,n,a[],ans;
bool pan(int x)
{
int a1=min(x,m);
for(int i=;i<=n;i++)
if(a[i]<x)
{
a1-=x-a[i];
if(a1<)
return ;
}
return ;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
l=;
r=;
for(;l<=r;)
{
int mid=(l+r)>>;
if(pan(mid))
{
l=mid+;
ans=mid;
}
else
r=mid-;
}
printf("%d\n",ans);
return ;
}

二分答案判断是否可行。

其实我还有一种想法,只是一直没对,以后要对拍一下。

 #include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
long long a[],n,m,sum,q1=0x7ffffffffLL,q2=0x7ffffffffLL;
bool f;
int main()
{
scanf("%lld%lld",&n,&m);
for(int i=;i<=n;i++)
scanf("%lld",&a[i]);
sort(a+,a+n+);
for(int i=;i<=n;i++)
{
if(m-(i-)*(a[i]-a[i-])<)
{
f=;
q1=m/(i-)+a[i-];
}
m-=(i-)*(a[i]-a[i-]);
if(sum+(i-)*(a[i]-a[i-])>a[i])
{
f=;
q2=(sum-(i-)*a[i-])/(-i);
}
if(f)
break;
sum+=(i-)*(a[i]-a[i-]);
}
printf("%lld",min(a[n],min(q1,q2)));
return ;
}
上一篇:THE DRUNK JAILER 分类: POJ 2015-06-10 14:50 13人阅读 评论(0) 收藏


下一篇:BZOJ 2196: [Usaco2011 Mar]Brownie Slicing( 二分答案 )