Codeforces Round #389 (Div. 2) E. Santa Claus and Tangerines 二分+贪心+记忆化搜索

2536次E. Santa Claus and Tangerinestime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputou。

2536次

E. Santa Claus and Tangerines

time limit per test
2 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

Santa Claus hasntangerines, and thei-th
of them consists of exactlyaislices.
Santa Claus came to a school which haskpupils. 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.

Letbibe
the number of slices thei-th pupil has in the end. Let Santa'sjoybe
the minimum among allbi's.

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

Input

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

The second line consists ofnpositive integersa1, a2, ..., an(1 ≤ ai ≤ 107),
whereaistands
for the number of slices thei-th tangerine consists of.

Output

If there's no way to present a tangerine or a part of tangerine to everyone, print⑴. Otherwise, print the maximum possiblejoythat
Santa can have.

Examples

input

3 2
5 9 3

output

5

input

2 4
12 14

output

6

input

2 3
1 1

output

Note

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

In the second example Santa should divide both tangerines, so that he'll be able to present two parts with6slices and two parts with7slices.

In the third example Santa Claus can't present2slices to3pupils
in such a way that everyone will have anything.

Source

Codeforces Round #389 (Div. 2, Rated, Based on Technocup 2017 - Elimination Round 3)

My Solution

题意:有n个橘子,每一个橘子可以分成ai瓣,但每次只能把 1个完全的橘子或由1些把构成的部份橘子 分成尽量相等的两部份,即如果瓣数是偶数则当前只能分成相等的2部份,如果是奇数则分成2部份其中1部份比另外一部份多1,然后把这些得到的橘子或瓣分给k个小朋友,其中小朋友们得到瓣数中的最小值是答案,要求这个答案尽量大

2分+贪心+记忆化搜索

由于每一个小朋友只能得到1个橘子或1些由瓣构成的部份橘子,所答案最大为max{ai} 这里ans 属于[1, 1e7],故在(0, 1e7 + 1)内]对答案进行2分(不会取到左右端点),

每次2分扫1遍ai数组,对每一个数在跑1个logai的递归求出这个ai可以弄出多少个瓣数大于等于u的有瓣构成的部份橘子。

这是算法是 O(nlognlogn) 显示会超时的,故对求ai可以弄出多少个u时把普通的递归改成记忆化搜索,

然后还是TLE了,斟酌到优先对ai大的进行计算可以记录尽量多的数据,故把ai排序,然后贪心,从大的开始扫,这样可以减少大量的重复计算

通过记忆化搜索+贪心的优化,< 2000ms

此时复杂度大概略大于 O(nlogn) 远小于 O(nlognlogn).

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL maxn = 1e6 + 8;

int a[maxn], n, k, dp[10*maxn];

inline int calc(int x, const int& u)
{
    if(x < u) return 0;
    if(dp[x] != 0) return dp[x];
    if(x / 2 < u){
        return dp[x] = 1;
    }
    else if(x & 1){
        dp[x] = calc(x / 2, u);
        return dp[x] += calc(x / 2 + 1, u);
    }
    else{
        return dp[x] = 2 * calc(x / 2, u);
    }
}

bool check(const int& u)
{
    LL s = 0;
    for(int i = n - 1; i >= 0; i--){  //排序以后从大的开始记忆化搜索,不然会超时
        s += calc(a[i], u);
    }
    //cout << u << " : " << s << " " << k << endl;
    if(s >= k) return true;
    else return false;
}

int main()
{
    #ifdef LOCAL
    freopen("e.txt", "r", stdin);
    //freopen("e.out", "w", stdout);
    LL T = 4;
    while(T--){
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);

    int ans = ⑴;
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }

    sort(a, a + n);
    int l = 0, r = 1e7 + 1, mid;
    while(l + 1 < r){
        mid = (l + r) >> 1;
        memset(dp, 0, sizeof dp);
        if(check(mid)){
            ans = max(ans, mid);
            l = mid;
        }
        else r = mid;
    }

    cout << ans << endl;


    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

Thank you!

------fromProLights

Codeforces Round #389 (Div. 2) E. Santa Claus and Tangerines 二分+贪心+记忆化搜索文章到此结束,字数约8673字,希望可以帮助到大家。屹东网往后会继续推荐Codeforces Round #389 (Div. 2) E. Santa Claus and Tangerines 二分+贪心+记忆化搜索相关内容。