Алгоритм Divide и Conquer в C++

Question

В некоторых онлайн-судьях есть одна проблема, что я не знаю, как принять ее.

Проблема выглядит содержащаяся в этом первая строка два числа

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; 
} 

Update1: Мой бинарный поиск решения (до сих пор не прошел срок):

#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

Got принял (наконец) с помощью двух бинарного поиска (каждый для нижней границы, а верхняя граница) с этим кодом:

#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; 
} 

Answer 2

Update

Идущий с двоичного поиска подход, здесь мой новый код:

// 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), поэтому вторая - , а не часть диапазона) и уменьшает диапазон, поэтому все элементы в диапазоне удовлетворяют условию. Сначала выполняется итеративная корректировка границ диапазона до тех пор, пока середина диапазона не станет частью результата или пока не станет ясно, что результата нет. Затем, если есть какой-либо результат, он рекурсивно проверяет поддиапазоны ниже и выше найденного результата, чтобы получить границы всего диапазона результатов.

Version 1

Вы имеете дело только с положительными числами больше нуля.

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

Для каждого суб-термина floor(X/a1), есть floor(X1/ai) <= floor(X2/ai) если X1 < X2. Таким образом, единственными возможными значениями X, приводящими к M, являются те, где floor(X1/ai) == floor(X2/ai) для всех i (или все ai).

Для каждого ai это точно диапазон X1=k*ai до X2=k*ai+(ai-1) для некоторых k.

Это означает, что если какое-либо решение существует, диапазон значений X будет находиться между k*min(ai) и (k+1)*min(ai) для некоторых 0 < k <= m.

Так что, возможно, стоит сначала получить диапазон возможных результатов, а затем проверить отдельные значения только в пределах диапазона.

Результирующий алгоритм:

// 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 3

Я считаю, что ожидаемое решение для этого - двоичный поиск.

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

Таким образом, вы можете сделать бинарный поиск, чтобы найти наименьшее значение х, что f(x) = M, с start = 0 и end = M*a_1, что и начальные ограничения для двоичного поиска.

Чтобы найти верхний предел для x, выполните другой бинарный поиск или просто выполните все значения в массиве, чтобы найти наименьший y, так что floor(y/ai) > floor(x/ai) для некоторого i.