cf D. Renting Bikes

http://codeforces.com/contest/363/problem/D

先对b和p排序,用二分求出可以租的车子的最大辆数,其中用mid以后的个人钱数去租前mid的价钱的车子。

 #include <cstdio>
#include <cstring>
#include <algorithm>
#define LL __int64
#define N 200000
using namespace std;
int n,m;
LL a;
LL p[N],b[N];
int max1; bool ok(int mid)
{
LL sum=;
for(int i=; i<mid; i++)
{
if(b[n-mid+i]>=p[i]) continue;
else if(p[i]>b[n-mid+i])
{
sum+=(p[i]-b[n-mid+i]);
}
}
if(sum>a) return false;
return true;
} int main()
{
while(scanf("%d%d%I64d",&n,&m,&a)!=EOF)
{
for(int i=; i<n; i++)
{
scanf("%I64d",&b[i]);
}
for(int i=; i<m; i++)
{
scanf("%I64d",&p[i]);
}
sort(p,p+m);
sort(b,b+n);
int l=,r=min(n,m);
max1=;
while(l<=r)
{
int mid=(l+r)>>;
if(ok(mid))
{
l=mid+;
max1=max(max1,mid);
}
else
{
r=mid-;
}
}
if(max1==)
{
printf("0 0\n");
continue;
}
else
{
LL ans=;
for(int i=; i<max1; i++)
{
ans+=p[i];
}
if(a>=ans)
{
printf("%d %d\n",max1,);
}
else
{
printf("%d %I64d\n",max1,ans-a);
}
}
}
return ;
}
上一篇:HS光流算法详解<转载>


下一篇:hdu 畅通工程再续