时间戳

首页 > 解决方案 > 我该如何处理这样的问题？

c++ - 我该如何处理这样的问题？

问题描述

各位晚上好。我不确定在这个平台上问这样的问题是否违反规则（如果是，请告诉我）。问题是“实践竞赛”。我可以完成 10 个测试用例中的 5 个，但我不确定这有什么问题。请提出任何更正/逻辑/提示...并且时间复杂度必须小于 O(n^2) （根据给定的输入）

在此处输入图像描述

我尝试的方法是：

int main() {
  /* Enter your code here. Read input from STDIN. Print output to STDOUT */
  signed long int t, n;
  scanf("%d", &t);
  for (int i = 1; i <= t; i++) {
    int count = 0;
    scanf("%d", &n);
    if (n <= 10)
      count = n;
    else {
      // count = 9;
      string s;
      s = to_string(n);
      int len = s.length();
      int x = n / (pow(10, len - 2));
      int h = x / 11;
      string y = to_string(x);
      if (y.length() <= 2)
        x = 0;
      count = (9 * (len - 1)) + x + h;
    }
    printf("%d\n", count);
  }
  return 0;
}

请提出任何您认为有帮助的建议。太感谢了。

标签： c++logic

解决方案

对于该问题，鉴于您正在处理的工作区域相对较小（小于 10^9 的漂亮数字的数量可以通过这些值的表格来合理处理），这里是一个使用 pre - 生成的所有漂亮数字按排序顺序排列的表格。

一旦建立了表格，只需进行二进制搜索以确定在输入值之前出现的漂亮数字的数量。表中最接近的漂亮数字的位置就是我们需要的漂亮数字的个数。

二进制搜索是通过利用<algorithm>函数std::upper_bound完成的。此函数将返回一个迭代器，指向大于搜索项的项。然后使用 来获取位置std::distance（我们减去 1，因为std::upper_bound会给我们提供大于搜索项的项）。

表的生成可以在编译时完成（手动，只是初始化一个数组），或者如果你很懒，可以在运行时用一个简单的循环生成。这是一种这样的解决方案：

#include <algorithm>
#include <vector>
#include <iostream>

std::vector<int> values;

int generate_value(int digit, int numTimes)
{
    int total = 0;
    for (int i = 0; i < numTimes; ++i)
        total = 10 * total + digit;
    return total;
}

// I'm lazy, so let the program generate the table for me
void generate_values()
{
    size_t curIdx = 0;
    values.push_back(0);
    for (int i = 1; i <= 9; ++i)
    {
        for (int j = 1; j <= 9; ++j)
            values.push_back(generate_value(j, i));
    }
    values.push_back(1111111111);
}

// does a binary search and returns the position of the beautiful number
int beautiful(int num)
{
    if (num == 0)
        return 1;

    // get iterator to closest number equaling the beautiful number
    auto iter = std::upper_bound(values.begin(), values.end(), num);

    // get distance from beginning of vector
    return std::distance(values.begin(), iter) - 1;
}

int main()
{
    generate_values();
    std::cout << beautiful(18) << "\n";;
    std::cout << beautiful(1) << "\n";;
    std::cout << beautiful(9) << "\n";;
    std::cout << beautiful(100500) << "\n";;
    std::cout << beautiful(33) << "\n";;
    std::cout << beautiful(1000000000) << "\n";;
}

输出：

10
1
9
45
12
81

表的大小总共有 83 个条目，因此对该表的二进制搜索将只需要log(83)检查即可找到该值，最多可以在表中进行 7 次探测。

推荐阅读