C++中的分而治之算法

Question

网上有个judge有这个问题，不知道怎么录取。

问题是第一行包含两个数字

N (0 < N < 2^18) 
M (0 < M < 2^20)

第二行包含 N 个数字

ai (0 < ai < 2^40)

问题是有多少 X 满意：

M = floor(X/a1) + floor(X/a2) + ... + floor(X/an)

我天真的解决方案：

#include<bits/stdc++.h>
using namespace std;

long long n,m,i,j,haha,sum;
int main()
{
    cin >> n >> m;
    haha = 0;
    long long ar[n+5];
    for(i = 0; i < n; i++) cin >> ar[i];
    sort(ar,ar+n);
    for(i = ar[0]+1; i < m*ar[0]; i++){
        sum = 0;
        for (j = 0; j < n; j++) sum += i/ar[j];
        if (sum == m) haha += 1;
        else if (sum >= m) break;
    }
    cout << haha << endl;
}

更新1： 我的二分查找方案（还是没过时限）：

#include<bits/stdc++.h>
using namespace std;

long long n,m,i,l,r,mid,ans,tmp,cnt,haha;
long long ar[2621440];
long long func(long long x){
    haha = 0;
    for (i = 0; i < n; i++) haha += x/ar[i];
    return haha;
}

int main()
{
    cin >> n >> m;
    for(i = 0; i < n; i++) cin >> ar[i];
    sort(ar,ar+n);
    l = ar[0];
    r = ar[0]*m;
    mid = (l+r)/2;
    tmp = func(mid);
    while (tmp != m){
        mid = (l+r)/2;
        tmp = func(mid);
        if (l == r) break;
        if (tmp < m) l = mid+1;
        else if (tmp > m) r = mid-1;
        else break;
    }
    ans = 0;
    if (tmp == m) ans += 1;
    cnt = mid;
    while (func(cnt-1) == m){
        ans += 1;
        cnt -= 1;
    }
    cnt = mid;
    while (func(cnt+1) == m){
        ans += 1;
        cnt += 1;
    }
    cout << ans << endl;
}

Answer 1

更新

使用二进制搜索方法，这是我的新代码：

// compute X/ai sum
long long summarize(long long ar[], long long n, long long X)
{
    long long sum = 0;
    for (long long i = 0; i < n; i++)
    {
        sum += X/ar[i];
    }
    return sum;
}

bool get_range(long long ar[], int n, int m, pair<long long, long long>& range)
{
    long long sum = 0;
    long long x;
    // reduce range
    while (range.first < range.second)
    {
        x = (range.first + range.second) / 2;

        sum = summarize(ar, n, x);
        if (sum < m)
        {
            range.first = x + 1;
        }
        else if (sum > m)
        {
            range.second = x;
        }
        else if (x == range.first)
        {
            return true; // single element
        }
        else
        {
            break;
        }
    }

    if (sum != m)
    {
        return false;
    }

    // check surroundings for lower / upper bound.
    sum = summarize(ar, n, range.first);
    if (sum != m)
    {
        auto r1 = make_pair(range.first + 1, x);
        if (get_range(ar, n, m, r1))
        {
            range.first = r1.first;
        }
        else
        {
            range.first = x;
        }
    }
    sum = summarize(ar, n, range.second - 1);
    if (sum != m)
    {
        auto r2 = make_pair(x + 1, range.second - 1);
        if (get_range(ar, n, m, r2))
        {
            range.second = r2.second;
        }
        else
        {
            range.second = x + 1;
        }
    }

    return true;
}


int main()
{
    int n, m;
    cin >> n >> m;
    long long *ar = new long long[n];
    long long ar_min = LLONG_MAX;
    for(long long i = 0; i < n; i++)
    {
        cin >> ar[i];
        ar_min = min(ar[i], ar_min);
    }
    // initial range of possible X values
    auto range = make_pair(m / (ar_min * n), m * ar_min);
    if (get_range(ar, n, m, range))
    {
        cout << (range.second - range.first) << endl;
    }
    else
    {
        cout << 0 << endl;
    }
}

核心功能是get_range函数，它取一个可能的范围（[range.first, range.second)，所以第二个是不是范围的一部分）并减少range 所以范围内的所有元素都满足条件。它首先迭代调整范围边界，直到范围的中间是结果的一部分，或者直到很明显范围内没有结果。然后，如果有任何结果，它会递归检查找到的结果下方和上方的 sub-ranges，以检索整个结果范围的边界。

版本 1

您只处理大于零的正数。

M = floor(X/a1) + floor(X/a2) + ... + floor(X/an)

对于每个 sub-term floor(X/a1)，如果 X1 < X2，则有 floor(X1/ai) <= floor(X2/ai)。因此，导致 M 的唯一可能 X 值是那些，其中 floor(X1/ai) == floor(X2/ai) 代表所有 i（或所有 ai）。

对于每个 ai，对于某些 k，这正是 X1=k*ai 直到 X2=k*ai+(ai-1) 的范围。

这意味着，如果存在任何解，对于某些 0 < k <= m.

，X 值的范围将在 k*min(ai) 和 (k+1)*min(ai) 之间

因此，首先获取可能结果的范围，然后仅检查范围内的各个值可能是值得的。

结果算法：

// compute X/ai sum
long long summarize(long long ar[], long long n, long long X)
{
    long long sum = 0;
    for (long long i = 0; i < n; i++)
    {
        sum += X/ar[i];
    }
    return sum;
}

int main()
{
    int n, m;
    cin >> n >> m;
    long long *ar = new long long[n];
    long long ar_min = LLONG_MAX;
    for(long long i = 0; i < n; i++)
    {
        cin >> ar[i];
        ar_min = min(ar[i], ar_min);
    }

    // lowest possible k
    long long k = m / (ar_min * n);
    // get the value k for a possible range of X values
    for (; k <= m; k++)
    {
        auto x = ar_min * (k + 1);
        long long sum = summarize(ar, n, x);
        if (sum > m)
        {
            break;
        }
    }
    long long X_min = k * ar_min, X_max = (k + 1) * ar_min;
    long long result = 0;
    // count possible X values
    for (long long x = X_min; x < X_max; x++)
    {
        long long sum = summarize(ar, n, x);
        if (sum == m)
        {
            ++result;
        }
        else if (sum > m)
        {
            break;
        }
    }

    cout << result << endl;
}

它比我最初预期的要复杂一些。我希望它仍然是某种改进。

Answer 2

我认为预期的解决方案是二分查找。

定义 f(x) = sum_i f(x/a_i)。不失一般性，假设 a_i 以递增的顺序给出。

显然，

f(0) = 0 < M
f(M*a_1) ≥ M
f(x) ≥ f(y) if x≥y

因此您可以进行二分搜索以找到 x 的最小值 f(x) = M，其中 start = 0 和 end = M*a_1 作为二分搜索的初始限制。

要找到 x 的上限，请进行另一个二分搜索或循环遍历数组中的所有值以找到最小的 y，使得 floor(y/ai) > floor(x/ai) 对于某些 i。

Answer 3

使用以下代码使用两个二进制搜索（每个用于下限和上限）（最终）被接受：

#include<bits/stdc++.h>
using namespace std;

long long n,m,i,l,r,mid1,mid2,ans,tmp,cnt,haha,k;
long long ar[26214400];
long long func(long long x){
    haha = 0;
    for (k = 0; k < n; k++) haha += x/ar[k];
    return haha;
}

int main()
{
    cin >> n >> m;
    for(i = 0; i < n; i++) cin >> ar[i];
    sort(ar,ar+n);
    l = ar[0];
    r = ar[0]*m;
    mid1 = (l+r)/2;
    tmp = func(mid1);
    while (l < r){
        mid1 = (l+r)/2;
        tmp = func(mid1);
        if (tmp < m) l = mid1+1;
        else if (tmp > m) r = mid1-1;
        else r = mid1-1;
    }
    mid1 = l; //lower bound
    l = ar[0];
    r = ar[0]*m;
    mid2 = (l+r)/2;
    tmp = func(mid2);
    while (l < r){
        mid2 = (l+r)/2;
        tmp = func(mid2);
        if (tmp < m) l = mid2+1;
        else if (tmp > m) r = mid2-1;
        else l = mid2+1;
    }
    mid2 = r; //upper bound
    while (mid1 <= mid2 and func(mid1) != m) mid1 += 1;
    while (mid2 >= mid1 and func(mid2) != m) mid2 -= 1;
    ans = mid2-mid1+1;
    cout << ans << endl;
}

C++中的分而治之算法

Divide and Conquer algorithm in C++

c++

algorithm

divide-and-conquer