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

3 2
5 9 3

5

2 4
12 14

6

2 3
1 1

⑴

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

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠