E. Santa Claus and Tangerines

V2AS问路

E. Santa Claus and Tangerines

阅读原文时间：2023年07月09日阅读：3

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Santa Claus has n tangerines, and the i-th of them consists of exactly a__i slices. Santa Claus came to a school which has k pupils. Santa decided to treat them with tangerines.

However, there can be too few tangerines to present at least one tangerine to each pupil. So Santa decided to divide tangerines into parts so that no one will be offended. In order to do this, he can divide a tangerine or any existing part into two smaller equal parts. If the number of slices in the part he wants to split is odd, then one of the resulting parts will have one slice more than the other. It's forbidden to divide a part consisting of only one slice.

Santa Claus wants to present to everyone either a whole tangerine or exactly one part of it (that also means that everyone must get a positive number of slices). One or several tangerines or their parts may stay with Santa.

Let b__i be the number of slices the i-th pupil has in the end. Let Santa's joy be the minimum among all b__i's.

Your task is to find the maximum possible joy Santa can have after he treats everyone with tangerines (or their parts).

Input

The first line contains two positive integers n and k (1 ≤ n ≤ 106, 1 ≤ k ≤ 2·109) denoting the number of tangerines and the number of pupils, respectively.

The second line consists of n positive integers a_1, _a_2, …, _a__n (1 ≤ a__i ≤ 107), where a__i stands for the number of slices the i-th tangerine consists of.

Output

If there's no way to present a tangerine or a part of tangerine to everyone, print -1. Otherwise, print the maximum possible joy that Santa can have.

Examples

Input

3 2
5 9 3

Output

Input

2 4
12 14

Output

Input

2 3
1 1

Output

-1

Note

In the first example Santa should divide the second tangerine into two parts with 5 and 4 slices. After that he can present the part with 5 slices to the first pupil and the whole first tangerine (with 5 slices, too) to the second pupil.

In the second example Santa should divide both tangerines, so that he'll be able to present two parts with 6 slices and two parts with 7 slices.

In the third example Santa Claus can't present 2 slices to 3 pupils in such a way that everyone will have anything.

题意：有n个橘子，然后每个有ai片，分给m个人，每个橘子能再分，如果当前ai为偶数对半分，奇数分成两份相差一个，然后问分给m个人后分得最少的人能分得的最大值是多少。

思路：二分+记忆化;

二分答案mid，然后判断当前的是否可以分成m个大于等于mid的值，判断的时候用记忆化搜索复杂度N*log(N)。

1 #include
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include
8 typedef long long LL;
9 int plice[1000005];
10 bool check(LL mid);
11 int dfs(int nc,int mid);
12 LL n,m;
13 using namespace std;
14 int ac[10000001];
15 int t = 0;
16 int vis[10000001];
17 const int BufferSize=1<<16; 18 char buffer[BufferSize],*head,*tail; 19 inline char Getchar() { 20 if(head==tail) { 21 int l=fread(buffer,1,BufferSize,stdin); 22 tail=(head=buffer)+l; 23 } 24 return *head++; 25 } 26 inline int read() { 27 int x=0,f=1;char c=Getchar(); 28 for(;!isdigit(c);c=Getchar()) if(c=='-') f=-1; 29 for(;isdigit(c);c=Getchar()) x=x*10+c-'0'; 30 return x*f; 31 } 32 int main(void) 33 { 34 //freopen("in.txt","r",stdin); 35 //freopen("out.txt","w",stdout); 36 37 while(scanf("%lld %lld",&n,&m)!=EOF) 38 { 39 LL sum = 0; 40 t = 1;LL maxx = 0; 41 for(int i = 0; i < n; i++) 42 { 43 plice[i] = read(); 44 sum += plice[i]; 45 maxx = max((LL)plice[i],maxx); 46 } 47 if(sum < m)printf("-1\n"); 48 else 49 { sort(plice,plice+n); 50 LL l = 1; 51 LL r = maxx; 52 LL id = -1; 53 while(l <= r) 54 { 55 LL mid = (l + r)/2; 56 if(check(mid)) 57 l = mid+1,id = mid; 58 else r = mid-1; 59 t++; 60 } 61 printf("%lld\n",id); 62 } 63 } 64 return 0; 65 } 66 bool check(LL mid) 67 { 68 LL cn = 0; 69 int i; 70 for(i = 0; i < n; i++) 71 { 72 if(plice[i] == mid) 73 { 74 cn++; 75 vis[mid] = t; 76 ac[mid] = 1; 77 } 78 else if(plice[i] > mid)
79 {
80 cn+=(LL)dfs(plice[i],mid);
81 }
82 }
83 if(cn >= m)return true;
84 else return false;
85 }
86 int dfs(int nc,int mid)
87 {
88 if(t == vis[nc])return ac[nc];
89 vis[nc] = t;
90 if(nc < mid)return ac[nc] = 0;
91 if(nc%2)
92 { if(nc/2 < mid)return ac[nc] = 1;
93
94 return ac[nc] = dfs(nc/2,mid)+dfs(nc/2+1,mid);
95 }
96 else
97 {if(nc/2 < mid) return ac[nc] = 1;
98 return ac[nc] = (LL)2*dfs(nc/2,mid);}
99 }
100 //

手机扫一扫

移动阅读更方便

你可能感兴趣的文章