cf D. Renting Bikes

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

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

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define LL __int64
 5 #define N 200000
 6 using namespace std;
 7 int n,m;
 8 LL a;
 9 LL p[N],b[N];
10 int max1;
11 
12 bool ok(int mid)
13 {
14     LL sum=0;
15     for(int i=0; i<mid; i++)
16     {
17         if(b[n-mid+i]>=p[i]) continue;
18         else if(p[i]>b[n-mid+i])
19         {
20             sum+=(p[i]-b[n-mid+i]);
21         }
22     }
23     if(sum>a) return false;
24     return true;
25 }
26 
27 int main()
28 {
29    while(scanf("%d%d%I64d",&n,&m,&a)!=EOF)
30    {
31        for(int i=0; i<n; i++)
32        {
33            scanf("%I64d",&b[i]);
34        }
35        for(int i=0; i<m; i++)
36        {
37            scanf("%I64d",&p[i]);
38        }
39        sort(p,p+m);
40        sort(b,b+n);
41        int l=0,r=min(n,m);
42        max1=0;
43        while(l<=r)
44        {
45            int mid=(l+r)>>1;
46            if(ok(mid))
47            {
48                l=mid+1;
49                max1=max(max1,mid);
50            }
51            else
52            {
53                r=mid-1;
54            }
55        }
56        if(max1==0)
57        {
58            printf("0 0
");
59            continue;
60        }
61        else
62        {
63            LL ans=0;
64            for(int i=0; i<max1; i++)
65            {
66                ans+=p[i];
67            }
68            if(a>=ans)
69            {
70                printf("%d %d
",max1,0);
71            }
72            else
73            {
74                printf("%d %I64d
",max1,ans-a);
75            }
76        }
77    }
78    return 0;
79 }

View Code