如何降低c语言中算法的时间复杂度？

Question

下面的代码接受一个整数t，然后再接受3个整数t次，并返回可以同时从两个不同整数中减去1的最大次数，而当只剩下0以上的1个整数时，程序停止。我已经解决了这个问题，但我想降低代码的时间复杂度，但我不知道怎么做。

#include <bits/stdc++.h>

using namespace std;

int main() {
long long t, r, g, b, arr[1000], count = 0;
bool isMax=true;
cin >> t;

for (long long i = 0; i < t; i++) {
    cin >> r >> g >> b;
    arr[0] = r;
    arr[1] = g;
    arr[2] = b;
    for (long long j = 0; j < 3; j++) {
        for (long long k = 0; k < 2; k++) {
            if (arr[k] > arr[k + 1]) {
                long long a = arr[k];
                long long b = arr[k + 1];
                arr[k] = b;
                arr[k + 1] = a;
            }
        }
    }
    count = 0;
    if (arr[2] == 1) {
        cout << 1 << endl;
    } else if (arr[0] + arr[1] <= arr[2]) {
        cout << arr[0] + arr[1] << endl;
    } else {
        while (arr[0] > 0) {
            while (isMax && arr[0] > 0) {
                arr[2]--;
                arr[0]--;
                count++;
                if (arr[2] < arr[1]) {
                    isMax = false;
                }
            }
            while (!isMax && arr[0] > 0) {
                arr[1]--;
                arr[0]--;
                count++;
                if (arr[1] < arr[2]) {
                    isMax = true;
                }
            }
        }
        while (arr[2] > 0 && arr[1] > 0) {
            arr[2]--;
            arr[1]--;
            count++;
        }
        cout << count << endl;
    }
}
}

如何在不使用所有这些增加时间复杂度的循环的情况下获得相同的输出？

编辑：我不想我的代码为我重新编写，这是家庭作业，我想要的是提示和帮助，这样我就可以减少时间复杂性，我不知道怎么做。

编辑2：在我的算法中，我按升序对3个数字进行排序，然后使用while循环检查最小的数字（s/arr[0]）是否正确

Answer 1

我不确定我是否正确理解了这个问题，但如果你想知道从三元素集中的两个元素中减去1直到达到零的最大次数，我相信答案应该与找到集合的中值元素相同。例如，如果我有一套

10 20 30

如果我总是选择从子集{20，30}中减去，那么我能减去1的最大次数是20次，而如果我总是选择从子集{10，20}中减去，那么最小次数是10。

希望这有帮助！（假设我没有完全误解这个问题）

编辑：

在澄清评论之后，我相信您需要做的就是在非最大元素和最大元素之间找到最小值。考虑以下示例：

例如，如果给你一个集合{80,10,210}，你的问题的答案是90，因为我们可以从子集{80,10}中减去10，留下{70,0,210}，我们可以从子集{70,210}中进一步减去70，留下{0,0140}，在那里我们不能执行更多的操作。我们用1进行了80次10=90的减法运算，在这种情况下，max=210，min med=90

另一方面，考虑集合{2,2,2}。我们可以从子集{2,2}中减去2，留下{0,0,2}，在那里我们不能执行更多的操作。在这种情况下，我们通过1 Max=2和min med=4执行了2次减法

最后一个例子：考虑集合{2,3,5}。我们可以从子集{2,3}中减去2，留下{0,1,5}，我们可以从子集{1,5}中减去1，从而得到{0,0,4}，在那里我们不能执行更多的操作。在这种情况下，我们通过1 Max=5和min med=5执行了2 3=5减法

如果您继续以这种方式执行示例，您应该能够说服自己解决方案总是最小（最大，最小中值）。

Answer 2

假设你的代码是正确的，你可以精确地检查你的循环在做什么，并从数学上看它们。

if ( arr[2] == 1 ) {
    cout << 1 << endl;
} else if ( arr[0] + arr[1] <= arr[2] ) {
    cout << arr[0] + arr[1] << endl;
} else {
    while ( arr[0] > 0 ) {
        if ( arr[2] > arr[1] ) {
            long long min = std::min( std::min( arr[0], arr[2] ), arr[2] - arr[1] + 1 );
            arr[0] -= min;
            arr[2] -= min;
            count += min;
        } else {
            long long min = std::min( std::min( arr[0], arr[1] ), arr[1] - arr[2] + 1 );
            arr[0] -= min;
            arr[1] -= min;
            count += min;
        }

    }
    count += std::min( arr[2], arr[1] );
    cout << count << endl;
}

假设你的程序是正确的，他会对我尝试的所有输入产生相同的结果。

Answer 3

我不确定我是否正确理解了这个问题。但如果我这样做了，你可以通过以下方式优化算法：

int count = 0;
int a = 20, b = 10, c = 21;
sort(a, b, c); // Function that sorts the numbers, so that a is the smallest and c is the largest
count += a;  // count = 10
c -= a;  // a = 10, b = 20, c = 11
if(c < b) {
    float diff = b - c; // diff = 9
    float distribute = diff / 2; // distribute = 4.5
    count += b - ceil(distribute); // count = 25
}
else count += b;

您必须将这个t乘以，然后对计数变量求和，从而导致t的复杂性。