首页 > 代码库 > Codeforces Round #211 (Div. 2) D题（二分，贪心）解题报告

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

2024-08-25 01:18:47   216人阅读

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

题目地址

简要题意：

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

思路分析：

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

　　参考代码：

 1 #include<stdio.h>
 2 #include<bits/stdc++.h>
 3 #include <iostream>
 4 using namespace std;
 5 typedef long long ll;
 6 int ren[100005],price[100005];
 7 ll an;
 8 int n,m,a,mid,l,r;
 9 bool check(int k)//检验函数，判断k个是否可行
10 {
11     int dui = n - k;//对应的下标
12     int tmp = a;
13     for(int i = 0;i < k;++i,dui++)
14     {
15         if(price[i] <= ren[dui]){
16             continue;
17         }
18         else if((price[i] > ren[dui])&&(price[i] <= ren[dui]+tmp)){
19             tmp -= (price[i]-ren[dui]);
20         }
21         else
22         {
23             return false;
24         }
25     }
26     return true;
27 }
28 int main()
29 {
30     int i;
31     scanf("%d%d%d",&n,&m,&a);
32     for(i=0;i<n;i++)
33     {
34         scanf("%d",&ren[i]);
35     }
36     for(i=0;i<m;i++)
37     {
38         scanf("%d",&price[i]);
39     }
40     sort(ren,ren+n);sort(price,price+m);
41     l=0;r=min(n,m);
42     while(l<=r)//二分查找
43     {
44         mid=(l+r)/2;
45         if(check(mid))
46         {
47             l=mid+1;
48         }
49         else
50             r=mid-1;
51     }
52     mid=l-1;
53     an=0;
54     for(i=0;i<mid;i++)
55     {
56         an+=price[i];
57     }
58     an=max(0ll,an-a);
59     printf("%d %I64d\n",mid,an);
60         return 0;
61 }

 

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


联系
我们