C++ 查找具有最大数字和的元素的范围查询

在这个教程中，我们讨论了在C++中使用范围查询查找具有最大数字和的元素的问题。为了解决这个问题，我们需要一个包含元素的数组和一些查询。这些查询表示数组的索引，并使用这些查询查找具有最大数字和的数组元素。最大数字和是两位数（个位和十位数字相加）或一位数的最高求和。例如：12，其和为3（1 + 2）。在这个教程中，通过使用这些查询找到一个具有最大求和的数。

为了实现这个方法，我们使用了两种方法：

• 原生方法

• 构建一个段树

演示1

a[] = {1, 44, 16, 11, 18}
Query = [1, 4]

输出

The maximum digit sum element is 18

解释

在上面的例子中，使用查询的子数组是{44, 16, 11, 18}。输入数组的起始索引是0。要找到具有最大数字和的元素，可以按以下方式相加两个数字：

44 = 4+4 = 8

16 = 1+6 = 7

11 = 1+1 = 2

18 = 1+8 = 9

最大和为9，具有最大和数字的元素是18。

演示2

a[] = {12, 44, 55, 45, 63}
Query = [2, 4]

输出

The maximum digit sum element is 55

解释

在上面的例子中，使用查询[2, 4]的子数组是{55, 45, 63}。要找到数字之和最大的元素，需要计算每个元素的和，如下所示：

55 = 5+5 = 10

45 = 4+5 = 9

63 = 6+3 = 9

最大和是10，具有这个最大和的元素是55。

C++库函数

语法

size(): 这是C++标准库的内置函数。它返回输入字符串的长度。

string_name.size();

pow() 函数： 它在 <cmath> 头文件中定义。它接受两个参数，并返回第一个参数的第二个参数次方。

pow(a, b);

vector： 它是C++中的动态数组，定义在vector头文件中。它的元素可以很容易地插入和删除。

vector<data_type> vector_name;

ceil(): 它在<cmath>头文件中定义。它接受一个参数并返回参数的最近大于或等于的值。

ceil(n);

sizeof（）： 它在C++标准库中定义。它在编译时计算变量、常量和数据类型的大小。

sizeof(variable);

步骤1

• 初始化一个元素数组 a[]。

• 定义用于找到元素索引的查询。

• 使用 for 循环遍历在查询中定义的数组索引。

• 通过将数字相加来计算每个元素的总和。

• 打印具有最大数字总和的数字。

示例1

我们使用简单的方法实现任务。在这个方法中，我们使用一个 for 循环遍历数组，其中的起始和结束范围在查询中定义。计算元素的总和，并打印具有最大数字总和的元素。

#include <iostream>
using namespace std;

// Function for calculating the digit sum 
int digitSum(int no){
    int result = 0;
    while (no > 0){
        result += no % 10;
        no /= 10;
    }
    return result;
}

// Function for finding the maximum sum digit number
int maximumDigitSum(int a[], int s, int i, int j){
    int maxs = -1, maxn = -1;
    for (int x = i; x <= j; x++){
        int result = digitSum(a[x]);
        if (result > maxs){
            maxs = result;
            maxn = a[x];
        }
        else if (result == maxs && a[x] > maxn){
            maxn = a[x];
        }
    }
    return maxn;
}

// code controller
int main(){
    // Input array
    int a[] = { 11, 14, 34, 51, 32 };

    int s = sizeof(a) / sizeof(a[0]);
    int i = 1, j = 4;
    cout << "The maximum digit sum number is : "<<maximumDigitSum(a, s, i, j) << endl;

    return 0;
}

输出

The maximum digit sum number is : 34

步骤2

• 初始化一个元素数组。

• 指定查询范围。

• 构建一个段树，其中每个节点表示一个元素数组。

  • 首先将段树分为两半，并且每个节点表示两个值。

  • 将值插入左右子节点。

• 段树中的每个节点都有两个值：数字和最大数字和。

• 使用查询定义的范围，在段树上遍历以找到最大数字和。

• 打印结果。

示例2

在这里，我们通过构建一个段树来实现这个问题。构建一个段树，并使用查询来找到最大数字和。递归地调用用户定义的函数maximumDigitSum来遍历段树并计算输出。

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

// Function to calculate the digit sum of a number
int digitSumNumber(int no){
    int result = 0;
    while (no > 0){
        result += no % 10;
        no /= 10;
    }
    return result;
}

// Function to build the segment tree
void buildSegmentTree(vector<int>& segtree, const vector<int>& a, int l, int h, int p){
    if (l == h){
        segtree[p] = a[l];
        return;
    }
    int m = (l + h) / 2;
    buildSegmentTree(segtree, a, l, m, 2 * p + 1);
    buildSegmentTree(segtree, a, m + 1, h, 2 * p + 2);
    segtree[p] = max(segtree[2 * p + 1], segtree[2 * p + 2]);
}

// Function to query the segment tree for maximum digit sum in a given range
int querySegTree(vector<int>& segtree, int i, int j, int l, int h, int p){
    if (i <= l && j >= h)
        return segtree[p];
    if (i > h || j < l)
        return 0;
    int m = (l + h) / 2;
    return max(querySegTree(segtree, i, j, l, m, 2 * p + 1),
               querySegTree(segtree, i, j, m + 1, h, 2 * p + 2));
}

// Function to initialize the segment tree
int maxDigitSum(const vector<int>& a, int s, int i, int j){
    int segTreeHeight = ceil(log2(s));
    int segTreeSize = 2 * pow(2, segTreeHeight) - 1;
    vector<int> segtree(segTreeSize);

    buildSegmentTree(segtree, a, 0, s - 1, 0);

    return querySegTree(segtree, i, j, 0, s - 1, 0);
}

int main(){
    vector<int> a = {12, 13, 45, 17, 10, 23};
    int s = a.size();
    int i = 1, j = 4;

    int number = maxDigitSum(a, s, i, j);

    cout << "Maximum digit sum in the range [" << i << ", " << j << "]: " << number << endl;

    return 0;
}

输出

Maximum digit sum in the range [1, 4]: 45

结论

我们已经完成了这个关于在一系列查询中找到数字最大的总和的教程。我们使用了两种方法来解决这个教程的任务：朴素方法和段树。通过一些例子展示了问题陈述，以便更好地理解它的目的。在C++实现中，我们初始化了一个数组并定义了查询范围，以找到数字最大的总和。