1

有一个自然数n。您必须找到一对自然数 x, y，其和为 n，并且在其他总和为 n 的对中能量最小。

Energy(x) = sum of all digits of x
Total Energy = Energy(x) + Energy(y)

1 <= n <= 10^9

For eg, 
n = 10000
A few pairs: 
5000 + 5000 -> Energy = 10
1000 + 9000 -> Energy = 10
9999 + 1 -> Energy = 37
2999 + 7001 -> Energy = 37

So possible answers are:
(5000, 5000), (1000, 9000) etc

到目前为止，我已经尝试过上面提到的解决方案，但这不是一种优化的方法

我将从 1 循环到 n-1 并尝试所有对并检查它们的数字总和，但对于大数字将花费太多时间。例如

n= 50

1,49--> energy 14
2,48--> energy 14
3,47--> energy 14
4,46--> energy 14
5,45--> energy 14
.
.
.
.
10,40-->energy 5

（已编辑）经过一番思考，我得出了以下解决方案。如果有人能提出更好的解决方案将不胜感激

public int sum(int n) {
    String s = String.valueOf(n);
    if (isNonZeroOnlyOne(n)) {
        int num = getNonZeroNo(n);
        if (num == 1)
            return 10;
        return num;
    }
    return calculateEnergy(s);
}

private int calculateEnergy(String s) {
    int sum = 0;
    for(int i=0; i<s.length(); i++)
        sum += s.charAt(i) - '0';
    return sum;
}

private int getNonZeroNo(int n) {
    String s = String.valueOf(n);
    for(int i=0; i<s.length(); i++) {
        char c = s.charAt(i);
        if (c != '0')
            return c-'0';
    }
    return '0';
}

private boolean isNonZeroOnlyOne(int n) {
    String s = String.valueOf(n);
    int count = 0;
    for(int i=0; i<s.length(); i++) {
        char c = s.charAt(i);
        if (c != '0')
            count++;
        if (count > 1)
            return false;
    }
    return true;
}
4

6 回答 6

2

这很简单。

如果 n 的类型为 10^x，则答案为 10。否则，答案为 n 的位数之和。

这里的想法是将数字分解成一对，其中包含的数字少于 n 中的数字。如果您分解为较小的数字，则总和与原始数字相同。例如 7 = 1-6,2-5,3-4。

对于像 100, 1000.... 这样的数字，数字 1 不能进一步分解成对，所以我们尝试将 10 作为数字的总和，这样总和就变成了 n。比如 10=5-5,2-8,3-7 100=20-80,40-60

对于其他数字，例如 123，它可以分解为 100-23、120-3、111-12……所有数字都会给你总和 6。这是原始数字的位数之和。

如果您尝试分解成更多对，例如 80-43、52-71，您会看到数字总和随着您分解为包含的数字高于 n 中的数字而增加。比如 8 4,5,7 大于 3。

于 2020-04-01T15:40:50.333 回答
1

最小的能量可以通过一个简单的公式得出。

1) 给定 N > 100，对可以是 N-100 和 100 ，并且能量将与 N 的能量相同。例如： N = 500 ；对 = 400 和 100 ；能量 = 5

2) N >=10 和 N <=100 ，对 = N-10 和 10 例如： N = 50 ；对 = 40 和 10 ; 能量 = 5

3) N >=2 和 N <=10 ，对 = N-1 和 1 例如： N = 5 ；对 = 4 和 1 ; 能量 = 5

于 2020-02-13T03:37:24.217 回答
0

我在这个问题上花了1个多小时。应该回答n = 1什么？所以我认为n应该大于1。我假设n > 1.

所以蛮力解决方案在这里不起作用，因为n它足够大。所以你需要更优化的解决方案。您需要考虑一下您必须carry 1在总和中制作多少次n。大多数9时候是这样！

如果你有一些基本的想法，digit-dp(Dynamic Programming)那么这个问题很容易。尝试将所有可能的数字放在 n 的位置上，并在其中取最小的能量。当您完全了解digit-dp技术时，这个问题很容易。你可以从这里和这里学习。

为了练习，你可以在这里找到很多问题（动态编程部分）。

供您参考，我刚刚编写了这段代码，它工作正常。希望你可以以此作为参考。

#include <bits/stdc++.h>

using namespace std;

const string INF_STRING = "9999999";
const int INF_INT = 9999999;

pair<string, int> INF = make_pair(INF_STRING, INF_INT);

int nod;
int digits[10];

int num_of_digits(int a) {
    int cnt = 0;
    while(a) {
        digits[cnt] = a % 10;
        a = a / 10;
        cnt++;
    }
    return cnt;
}

pair<string, int> dp[10][2][2][2];

pair<string, int> solve(int ind, int carry, bool is1, bool is2) {
    if(ind >= nod) {
        if(carry != 0 ||  !is1 || !is2) return INF;
        return make_pair("", 0);
    }
    pair<string, int> &ret = dp[ind][carry][is1][is2];
    if(ret.second != -1) return ret;
    ret = INF;
    for(int i = 0; i < 10; i++) {
        for(int j = 0; j < 10; j++) {
            int s = (i + j + carry);
            pair<string, int> cur = INF;
            if(s % 10 == digits[ind]) {
                cur = solve(ind + 1, s / 10, is1 || (i > 0? 1:0), is2 || (j > 0? 1:0));
            }
            if((cur.second + i + j) < ret.second) {
                ret.second = cur.second + i + j;
                ret.first =  cur.first + (char)(i + '0');
            }
        }
    }
    return ret;
}

int stringToInt(string num) {
    stringstream ss;
    ss<<num;
    int ret;
    ss >> ret;

    return ret;
}

int main() {
    int i, t, cases = 1, j, k, pos;
    int n;

    scanf("%d", &n);
    nod = num_of_digits(n);

    for(int i = 0; i < 10; i++) {
        for(int j = 0; j < 2; j++) {
            dp[i][j][0][0] = make_pair(INF_STRING, -1);
            dp[i][j][0][1] = make_pair(INF_STRING, -1);
            dp[i][j][1][0] = make_pair(INF_STRING, -1);
            dp[i][j][1][1] = make_pair(INF_STRING, -1);
        }
    }

    pair<string, int> res = solve(0, 0, 0, 0);

    string num1_str = res.first;
    int num1 = stringToInt(num1_str);
    int num2 = n - num1;

    printf("Minimum Energy: %d\n", res.second);
    printf("Num1 = %d, Num2 = %d\n", num1, num2);


    return 0;
}

/*
Input:
10000

Output:
Minimum energy: 10
Num1 = 1000, Num2 = 9000

*/
于 2020-02-12T09:04:40.517 回答
0

这是javascript中简单的答案。

function calculateEnergy(n) {
  let e = 0    
  while(n > 0) {
    e += n % 10
    n = Math.floor(n / 10)
  }
  return e
}


function countMinEnergy(n) {
  let minE = n
  let i = 1
  while(i <= n/2) {
    let e = calculateEnergy(i) + calculateEnergy(n - i)
    minE = e < minE ? e : minE
    i++
  }
  return minE
}

countMinEnergy(4325)

于 2020-05-17T04:43:40.800 回答
0

这是斯卡拉解决方案

object LeastEnergyPair extends App {
    
      private def getCountOfPair(array: Array[Int],sum: Int): mutable.Set[(Int, Int)] = {

    val seen =  mutable.Set[Int]()
    val out = mutable.Set[(Int,Int)]()

    array map { x =>
      val target = sum - x
      if (seen.contains(target) || target*2 == sum)
        out += ((Math.min(x,target),Math.max(x,target)))
      else
        seen += x
    }
    println(out)
    out
  }


  private def sum(i:Int): Int = i.toString.toCharArray.map(_.asDigit).sum


  def findLeastEnergyPair(a: mutable.Set[(Int,Int)]): (Int,Int) = {
    var min = Int.MaxValue
    var minPair = (0,0)
    a.foreach {
      case (i,j) =>
        if (sum(i) + sum(j) < min) {
          min = sum(i) + sum(j)
          minPair = (i,j)
          println(s"$min ----- $minPair")
      }
    }
    minPair
  }

  println(findLeastEnergyPair(getCountOfPair((1 to 10000).toArray, 10000)))
}
于 2021-02-13T14:30:09.400 回答
-1

以下逻辑将涵盖所有场景

if (N%10 == 0) {

      x1= (N/10);
      x2 = N-x1
}else{

     x1 = N-10; 
     x2 = 10;
}
于 2020-02-13T09:41:39.380 回答