国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > php开源 > 综合技术 > Codeforces Round #389 (Div. 2) E. Santa Claus and Tangerines 二分+贪心+记忆化搜索

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

来源:程序员人生   发布时间:2017-02-24 11:08:35 阅读次数:2595次

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 has n tangerines, and the i-th of them consists of exactly ai 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 bi be the number of slices the i-th pupil has in the end. Let Santa's joy be the minimum among all bi'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 ≤ 1061 ≤ k ≤ 2·109) denoting the number of tangerines and the number of pupils, respectively.

The second line consists of n positive integers a1, a2, ..., an (1 ≤ ai ≤ 107), where ai 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 . Otherwise, print the maximum possible joy that 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 with 5 and 4 slices. After that he can present the part with 5slices 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 7slices.

In the third example Santa Claus can't present 2 slices to 3 pupils 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!

                                                                                                                                               ------from ProLights

生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生