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個(gè)橘子，每一個(gè)橘子可以分成ai瓣，但每次只能把 1個(gè)完全的橘子或由1些把構(gòu)成的部份橘子 分成盡量相等的兩部份，即如果瓣數(shù)是偶數(shù)則當(dāng)前只能分成相等的2部份，如果是奇數(shù)則分成2部份其中1部份比另外一部份多1，然后把這些得到的橘子或瓣分給k個(gè)小朋友，其中小朋友們得到瓣數(shù)中的最小值是答案，要求這個(gè)答案盡量大

2分+貪心+記憶化搜索

由于每一個(gè)小朋友只能得到1個(gè)橘子或1些由瓣構(gòu)成的部份橘子，所答案最大為max{ai} 這里ans 屬于[1, 1e7]，故在(0, 1e7 + 1)內(nèi)]對答案進(jìn)行2分(不會(huì)取到左右端點(diǎn))，

每次2分掃1遍ai數(shù)組，對每一個(gè)數(shù)在跑1個(gè)logai的遞歸求出這個(gè)ai可以弄出多少個(gè)瓣數(shù)大于等于u的有瓣構(gòu)成的部份橘子。

這是算法是 O(nlognlogn) 顯示會(huì)超時(shí)的，故對求ai可以弄出多少個(gè)u時(shí)把普通的遞歸改成記憶化搜索，

然后還是TLE了，斟酌到優(yōu)先對ai大的進(jìn)行計(jì)算可以記錄盡量多的數(shù)據(jù)，故把a(bǔ)i排序，然后貪心，從大的開始掃，這樣可以減少大量的重復(fù)計(jì)算

通過記憶化搜索+貪心的優(yōu)化， < 2000ms

此時(shí)復(fù)雜度大概略大于 O(nlogn) 遠(yuǎn)小于 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--){  //排序以后從大的開始記憶化搜索，不然會(huì)超時(shí)
        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

生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)