c++ - 三个数中的最大成对递减数

Question

给定的是 3 个非负整数 a,b,c

在单个操作中，我们必须从两个整数中减去 1，前提是它们不会变为负数。

我们必须找到可能的最大操作数，直到给定操作不可能为止。

约束：1<=a,b,c<=10^18 , 1<=test-cases<=10^5

示例：
(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";
   }
}

更新：事实证明我的解决方案是正确的，这是完全相同的问题和社论

标签： c++algorithmmath

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('');
}