Максимальное количество попарных уменьшений в трех числах

Question

Даны 3 неотрицательных целых числа a, b, c

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

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

ограничения: 1 <= a, b, c <= 10 ^ 18 , 1 <= контрольные примеры <= 10 ^ 5 </strong>

Примеры:
(1,2,3) -> (1,1,2) -> (1,0,1 ) -> (0,0,0), ответ 3
(1,1,8) -> (1,0,7) -> (0,0,6), ответ 2

Любой подход или доказательство будут очень полезны.

Я действительно написал код, который работает, насколько я знаю, но я не знаю, полностью ли это верно.

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

#define fastio ios_base::sync_with_stdio(0); cin.tie(0)
#define LL long long 

int main(){
   fastio;
   int t; cin>>t;
   while(t--){
      LL a[3]; cin>>a[0]>>a[1]>>a[2];
      sort(a,a+3);
      if(a[0]+a[1]>=a[2]){
         LL ans = a[2] + (a[0]+a[1]-a[2])/2;
         cout<<ans;
      }
      else {
         LL ans = a[1] + min(a[0],a[2]-a[1]);
         cout<<ans;
      }
      cout<<"\n";
   }
}

ОБНОВЛЕНИЕ : оказывается, мое решение верное, вот та же самая проблема и редакционная

Answer 1

Разве это не просто:

Сортировка чисел

1 2 3

total 0

Вычтите первое (и прибавьте к итоговому) так, чтобы второе стало как можно ближе, хотя и меньше или равно третьему

0 2 2

total 1

Вычтите второе и прибавьте к сумме

0 0 0

total 3

?

2 2 2
0

0 1 1
2

0 0 0
3

function f(arr){
  arr.sort((a, b) => a - b);
  
  let [a, b, c] = arr;
  const max_from_c = c - b;
  
  if (max_from_c >= a)
    return a + b;

  let total = max_from_c;
  
  a = a - max_from_c;
  c = c - max_from_c;
  const smaller_half = Math.floor(a / 2);
  const larger_half = a < 2 ? a : Math.ceil(a / 2);
  c = c - larger_half;
  total = total + larger_half;
  b = b - smaller_half;
  total = total + smaller_half;

  return total + Math.min(b, c);
}

var arrays = [
  [1,2,3], // 3
  [1,1,8], // 2
  [3,4,5], // 6
  [1,1,1], // 1
  [1,1,2], // 2
  [2,1,2], // 2
  [2,2,2], // 3
  [3,3,2], // 4
  [10000,10000,10000] // 15000
];

for (let arr of arrays){
  console.log(JSON.stringify(arr));
  console.log(f(arr));
  console.log('');
}

Answer 2

Мне потребовалось три попытки, чтобы понять это правильно. Ошибка в этой задаче как в задаче динамического программирования c заключалась в нисходящей спирали

. Хитрость заключается в том, чтобы признать, что ее можно решить за все время oop, где вы постоянно сортируете a,b,c от наименьшего к наибольшему. Затем оцените, к какой схеме подходят цифры. Шаблоны для поиска включают:

• 1 или менее положительных значений в наборе: a=0, b=0, c=5
• 2 положительных значения и ноль в наборе: a=0, b=3, c=10
• 3 положительных значения, все разные: a=5, b=11, c=88
• 3 положительных значения, все одинаковые: a=10, b=10, c=10
• 3 положительных значения, наименьшие два равны: a=5, b=5, c=22
• 3 положительных значения, самые большие два равны: a=3, b=5, c=5

После того, как вы выясните, какой шаблон a,b,c попадает в приведенный выше список, есть специфика c express сокращения, которые могут быть сделаны. Многие из которых позволят вам вырваться из l oop без необходимости дальнейшего уменьшения набора. И я думаю, что следующий код работает так, что он повторяется только через l oop не более 2 (или 3) раз. Следовательно, это O (1) решение .

#include <iostream>
#include <algorithm>

using namespace std;

long long maxDeductions(long long a, long long b, long long c)
{
    long long total = 0;  // this is the running count of "deduction" steps made so far

    while (true)
    {
        long long deduction = 0;  // scratch variable for math

        // sort a,b,c into ascending order
        long long sorttable[3] = { a,b,c };
        sort(sorttable, sorttable + 3);
        a = sorttable[0];  // smallest
        b = sorttable[1];  // middle
        c = sorttable[2];  // largest

        // count the number of positive values among a,b,c    
        int positives = 0;
        positives += (a > 0);
        positives += (b > 0);
        positives += (c > 0);

        if (positives <= 1)
        {
            // Nothing left to do, we can break out of the loop
            break;
        }
        else if (positives == 2)
        {
            // When there are only two positives left
            // The number of deductions that can be express computed.
            // as the smaller of the remaining positive values, that is: b
            //
            // ASSERT: (b <= c) && (b > 0) && (c > 0)
            deduction = b;
            total += deduction;
            break;
        }
        else // three positives
        {
            if ((a != b) && (b != c))    // 3 positives, all different
            {
                // reduce the two larger values, b and c,  by the delta between b and a
                // this "b-a" amount is the number of deductions computed to  get the set a,b,c to have 
                // at least 2 identical numbers for the next set
                deduction = b - a;
                b = a;
                c -= deduction;
                total += deduction;
            }
            else if ((a == b) && (b == c)) // 3 positives, all the same
            {
                // when you have 3 identical values: N,N,N
                // It takes three steps to get to N-2,N-2,N-2
                // With a subtle tweak for odd vs even values of N, simple math can be used to 
                // deduce the remaining number of deductions

                if (a % 2) // odd
                {
                    deduction = ((a - 1) / 2) * 3 + 1;
                }
                else  // even
                {
                    deduction = (a / 2) * 3;
                }
                total += deduction;
                break;
            }
            else if (c == b)   // 3 positives, largest two are the same, equivalent to all different
            {
                deduction = b - a;
                b = a;
                c -= deduction;
                total += deduction;
            }
            else if (a == b)   // 3 positives, smallest two are the same
            {
                // this is the tricker one, but you can quickly see the pattern:
                // NNZ reduces in N*2 steps.  Example for N=5
                // 559 -> 548 -> 448 ->  437 -> 337 -> 326 -> 226 -> 215 -> 115 -> 104 -> 003
                // You can see every two reductions steps gets N,N,Z reduced to N-1,N-1,Z-1
                // Hence, exactly N*2 steps remaining
                total += (a * 2);
                break;
            }
        }

    }
    return total;
};