# 2016 ACM-ICPC Asia China-Final D 二分

``` 1 //#include "bits/stdc++.h"
2 #include "cstdio"
3 #include "map"
4 #include "set"
5 #include "cmath"
6 #include "queue"
7 #include "vector"
8 #include "string"
9 #include "cstring"
10 #include "time.h"
11 #include "iostream"
12 #include "stdlib.h"
13 #include "algorithm"
14 #define db double
15 #define ll long long
16 //#define vec vector<ll>
17 #define Mt  vector<vec>
18 #define ci(x) scanf("%d",&x)
19 #define cd(x) scanf("%lf",&x)
20 #define cl(x) scanf("%lld",&x)
21 #define pi(x) printf("%d\n",x)
22 #define pd(x) printf("%f\n",x)
23 #define pl(x) printf("%lld\n",x)
24 #define rep(i, x, y) for(int i=x;i<=y;i++)
25 const int N   = 1e6 + 5;
26 const int mod = 1e9 + 7;
27 const int MOD = mod - 1;
28 const db  eps = 1e-18;
29 const db  PI  = acos(-1.0);
30 using namespace std;
31 int t,n,k;
32 ll a[N],b[N];
33 bool cal(int x)
34 {
35     int p=x;
36     for(int i=0;i<x;i++){
37         b[i]=a[i];
38     }
39     for(int i=x;i<x*k;i++){//判断是否可以构成x个
40         while(b[i-x]*2>a[p]&&p<n) p++;
41         if(p==n) return 0;
42         b[i]=a[p++];
43     }
44     return 1;
45 }
46 int main()
47 {
48     ci(t);
49     for(int ii=1;ii<=t;ii++)
50     {
51         ci(n),ci(k);
52         memset(a,0, sizeof(a));
53         memset(b,0, sizeof(b));
54         for(int i=0;i<n;i++) cl(a[i]);
55         sort(a,a+n);
56         int l=0,r=n/k;//二分的上下界
57         while(l<r)
58         {
59             int m=l+(r-l+1)/2;
60             if(cal(m)==1) l=m;
61             else r=m-1;
62         }
63         printf("Case #%d: %d\n",ii,l);
64     }
65 }```

2016 ACM-ICPC Asia China-Final D 二分

(0)
(0)

0条