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

My Solution

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

二分+贪心+记忆化搜索

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

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

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

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

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

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

#include 
#include 
#include 
#include 
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 = -1;
    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;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx