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

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈