主页 / 问题 / 1275743
Accepted
Null
Asked:2022-04-28 03:28:28 +0000 UTC2022-04-28 03:28:28 +0000 UTC

任务优化

  • 772

有这样一个任务：

在此处输入图像描述

我试着这样做：

#include <iostream>
using namespace std;

bool check(int a, int b, int c){
    return a < b + c && b < a + c && c < a + b;
}

int main() {
    int a, b, c, d, count = 0;
    cin >> a >> b >> c >> d;
    for (int x = a; x <= b; x++){
        for (int y = b; y <= c; y++){
            for (int z = c; z <= d; z++){
                count += check(x, y, z);
            }
        }
    }
    cout << count;
}

她没有通过一项测试。我认为完整的搜索需要很多时间。请告诉我如何以另一种方式解决此问题或改进此问题。

c++

1 个回答

  1. Best Answer

    你需要坐下来仔细写下选项。显然，由于 A,B,C,D 的非递减序列，只需要检查条件 x+y>z。

    假设我们已经有了 x 和 y。然后

    C <= z <= x+y-1
C <= z <= D

    那些。C <= z <= min(D,x+y-1)，所以对于给定的 x 和 y 你必须min(D,x+y-1)-C+1在结果中添加三角形，如果这个数字不小于零:) 已经得到 O(n^2)，但它仍然很多......

    假设有 x - y 可以是什么？这里有必要把它分成几部分：

    x+y-1 <= D

    和

    x+y-1 >= D+1

    再次绘制最小值、最大值和两个总和。

    “我们将把它留给读者作为练习”（c）:)

    由此产生的 O(n) 已经足够了，当然，一个人可以玩得更多，但复杂性已经开始超出规模。

    您还需要考虑int将这些数字相乘时可能还不够，因此最好使用long long.

    所有这些都转化为朴实无华的代码。

    int main(int argc, char * argv[])
{
    long long A, B, C, D;
    long long count = 0;
    cin >> A >> B >> C >> D;
    for(long long x = A; x <= B; ++x)
    {
        long long delta = 0;
        if (C >= max(B,D-x+2)) delta = (D-C+1)*(C - max(B,D-x+2) + 1);

        long long m = max(C-x,B), M = min(C, D+1-x);
        if (m <= M) delta += (2*x-2*C+m+M)*(M-m+1)/2;

        count += delta;
    }
    cout << count << endl;
}

    它完全通过了测试（您徒劳地隐藏了它；当有 URL 时，它更容易工作，并且您可以预先检查提出的解决方案作为问题的答案）。

    • 3

相关问题