Codeforces Round #211 (Div. 2) D题(二分,贪心)解题报告

---恢复内容开始---

题目地址

简要题意:

  n个小伙子一起去买自行车,他们有每个人都带了一些钱,并且有公有的一笔梦想启动资金,可以分配给任何小伙子任何数值,当然分配权在我们的手中。现在给出m辆自行车的价格,需要你求出最多可以让多少个小伙子有属于自己的自行车(即自行车不可以两个人共有,只能一个人有),和在满足之前这个条件的情况下,通过最省私人钱的分配,最少需消耗多少私人的资金。

思路分析:

  首先考虑,如何分配才是使其中x个小伙子能有自己车的最好分配方法。不难想到,将n个小伙子按个人资金从大到小排序,将m辆自行车的价格从小到大排序,使前x个有钱的小伙子依次去买第x便宜的车,第x-1便宜的车……最便宜的车。这就是最可行的分配方式,而如果对于x,这个都无法满足,那么就一定不存在可以使x个小伙子有自己的车的办法。由此,可以考虑二分查找最后一个满足这种情况的x。

  参考代码:

 #include<stdio.h>
#include<bits/stdc++.h>
#include <iostream>
using namespace std;
typedef long long ll;
int ren[],price[];
ll an;
int n,m,a,mid,l,r;
bool check(int k)//检验函数,判断k个是否可行
{
int dui = n - k;//对应的下标
int tmp = a;
for(int i = ;i < k;++i,dui++)
{
if(price[i] <= ren[dui]){
continue;
}
else if((price[i] > ren[dui])&&(price[i] <= ren[dui]+tmp)){
tmp -= (price[i]-ren[dui]);
}
else
{
return false;
}
}
return true;
}
int main()
{
int i;
scanf("%d%d%d",&n,&m,&a);
for(i=;i<n;i++)
{
scanf("%d",&ren[i]);
}
for(i=;i<m;i++)
{
scanf("%d",&price[i]);
}
sort(ren,ren+n);sort(price,price+m);
l=;r=min(n,m);
while(l<=r)//二分查找
{
mid=(l+r)/;
if(check(mid))
{
l=mid+;
}
else
r=mid-;
}
mid=l-;
an=;
for(i=;i<mid;i++)
{
an+=price[i];
}
an=max(0ll,an-a);
printf("%d %I64d\n",mid,an);
return ;
}
上一篇:【iOS开发】关于显示一连串图片组成动画效果UIImageView的使用


下一篇:mybatis源码解析7---MappedStatement初始化过程