最后一个TLE,是复杂度的问题吗
查看原帖
最后一个TLE,是复杂度的问题吗
1281794
postpone楼主2024/3/16 02:09

检查了下代码,没发现会死循环的点,代码如下

// luogu P2249 erfen
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
using ll = long long;
const ll inf = pow(2, 31) - 1;
const int N = 1e6 + 100;
int a[N], b[N];
int n, m;
int erfen(int l, int r, int x)
{
    int res = -1, mid;
    while (l <= r)
    {
        mid = l + ((r - l) >> 1);
        if (a[mid] < x)
            l = mid + 1;
        else if (a[mid] > x)
            r = mid - 1;
        else
        {
            res = mid;
            break;
        }
    }
    while (a[res] == a[res - 1] && res > 1)
        res--;
    return res;
}

void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= m; i++)
        cin >> b[i];
    for (int i = 1; i <= m; i++)
        cout << erfen(1, n, b[i]) << ' ';
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _ = 1;
    while (_--)
        solve();
    return 0;
}
2024/3/16 02:09
加载中...