c++ - Google KickStart Round B Bus Routes Problem 错误答案？

问题描述

我正在练习 google kickstart 的 B 轮公交路线问题。我实际上查看了他们的分析并实施了他们的替代答案。

我还将在我的代码下方粘贴问题提示。 https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ffc8/00000000002d83bf

我的解决方案通过了第一个测试集，但在第二个测试集上得到了错误的答案。我不知道第二个测试集是什么，只知道它非常大。我很困惑，因为我的解决方案遵循问题的分析，实际上是对 T 提供的替代解决方案的实现。我也不知道如何找出哪个测试用例可能给出错误的答案，似乎有这么多的可能性！

我什至不知道如何调试这样一个模糊的答案。也许有一些我没有考虑的边缘情况？


    #include <iostream> // includes cin to read from stdin and cout to write to stdout
        #include <bits/stdc++.h> 

        using namespace std; 

        int main() {
          int t, n, d;

          cin >> t; // read t. cin knows that t is an int, so it reads it as such.

          for (int i = 1; i <= t; ++i) {
            cin >> n >> d; // read n and then m.

            stack <int> bus;


            for(int j=0; j<n; j++){
                int x;
                cin >> x;
                bus.push(x);
            }


            while(!bus.empty()){
                int b = bus.top();
                bus.pop();
                d = d -  d%b;

            }

            cout << "Case #" << i << ": " << d << endl;

          }

          return 0;
        }

****这是问题提示的简化版本****

问题桶正计划乘坐公共汽车穿越乡村进行一段很长的旅程。她的旅程由 N 条公交路线组成，按照她必须乘坐的顺序从 1 到 N 编号。公共汽车本身非常快，但不经常运行。第 i 条公交路线仅每 Xi 天运行一次。

更具体地说，她只能在Xi、2Xi、3Xi等天乘坐第i班车。由于公共汽车很快，她可以在同一天乘坐多辆公共汽车。

Bucket 必须在 D 天完成她的旅程，但她希望尽可能晚地开始旅程。她最迟哪一天可以乘坐第一班公共汽车，并且仍然在 D 天完成她的旅程？

可以保证 Bucket 有可能在 D 天完成她的旅程。

输入输入的第一行给出了测试用例的数量，T.T 测试用例紧随其后。每个测试用例都以包含两个整数 N 和 D 的行开始。然后，另一行包含 N 个整数，第 i 个是 Xi。

输出对于每个测试用例，输出一行包含 Case #x: y，其中 x 是测试用例编号（从 1 开始），y 是她可以乘坐第一班公共汽车的最晚一天，并且仍然在 D 天完成她的旅程。

限制时间限制：每个测试集 10 秒。内存限制：1GB。

标签： c++algorithmsortingoptimization

我的猜测是使用int是不够的，因为D在测试集 2 中最多可以达到 10^12

编辑：我验证了我的猜测。您将能够通过修复此错误来解决问题。而且我相信在long long编码竞赛中使用是很常见的，即每次都要注意输入/输出约束。

c++ - Google KickStart Round B Bus Routes Problem 错误答案？

问题描述

解决方案

推荐阅读