csdn里的小T找糖豆。

csdn里的题目小T找糖豆。

已知序列A，包含1e18个元素，分别是[1,1e8]。现在去除序列中的n个元素. 序列中最小元素是？

第一行输入整数n。(1<=n<=100) 第二行输入n个整数。

输出序列中的最小元素。

示例：

输入：3 2 1

输出：4

#include
#include

int solution(int m, int arr1[]){
int result;

double i;                                           //填空起始
int t;
for(i=1;i<=1e18;i++)
{
    for(t=0;(double)arr1[t]>0;t++)
    {
        if(i==(double)arr1[t])
            break;
    }
    if(t==m)
    {
        result=i;
        break;
    }
}                                                   //填空结束

return result;

}

int main() {
int n;
scanf("%d", &n);

int *arr;
arr = (int*)malloc(n * sizeof(int));

for (int i = 0; i < n; i++)
{
    scanf("%d", &arr[i]);
}
    
int result = solution(n, arr);

printf("%d", result);

return 0;

}

问题就是不知道哪里错了，示例是对的，但是是提交时它说未通过所有测试例子，请看到我帖子的，帮忙看一看。

到底是1e8还是1e18
1e18是老大一个数了，int根本放不下
而且int型不要和double型做相等比较

这段代码存在两个问题：

1.使用双重循环遍历序列A，时间复杂度为O(n*1e18)，显然会超时。因为序列A有1e18个元素，而n最大为100，所以遍历整个序列A会花费非常长时间。

2.在比较过程中，double类型的i和int类型的arr1[t]进行比较，可能会出现精度误差。

解决方案：
1.考虑其他更快的算法来遍历序列A，比如线段树、哈希表等，时间复杂度更低。
2.使用long long int类型来遍历序列A。

最后，提醒您一点，在编程中，一定要考虑时间复杂度和精度误差等问题。

这个代码的问题在于它的算法复杂度是O(n * 10^18)，这意味着如果n为100，那么程序就要枚举10^20次。这是不可行的，因为一个普通的电脑可能在几秒内运行不到10^18次。

为了解决这个问题，你可以使用一个更高效的算法，例如二分查找。它的复杂度是O(nlogn)，而不是O(n)。

下面是一个实现二分查找的代码示例：


#include <iostream>
#include <algorithm>
using namespace std;

int n, m;
bool flag[1000001];

bool check(int x) {
    int cnt = 0;
    for (int i = 1; i <= 100000000; i++) {
        if (flag[i]) continue;
        if (x >= i) cnt++;
    }
    return cnt >= m;
}

int main() {
    cin >> n >> m;
    int x;
    for (int i = 0; i < n; i++) {
        cin >> x;
        flag[x] = true;
    }
    int l = 1, r = 100000000;
    while (l < r) {
        int mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << endl;
    return 0;
}

csdn里的 小T找糖豆。

csdn里的小T找糖豆。