526互联

Codeforces Round 905 (Div. 2) D1. Dances (Easy version)（贪心+二分）

发布时间 2023-10-23 21:16:12作者: ikunhuaji

Codeforces Round 905 (Div. 2) D1. Dances (Easy version)

思路：

对于 \(a\)，它的头默认为 \(1\)，则 \(a_0\) = \(1\)

对于排完序的 \(a\) 与 \(b\) 数组

最优为从 \(a\) 的结尾删除，从 \(b\) 的开头删除

二分保留位数，删去 \(n-mid\) 位,即 \(a\) 从 \(0\) 开始，\(b\) 从 \(k\)（\(k=n-mid\)）开始

\(a_0\) ~ $a_{mid-1} $ 与 \(b_k\) ~ $b_{n-1} $ 比较大小

若满足则右移\(mid\)，更新最大的满足保留位数

则最小删去数为 \(n - l\)

#define int long long
#define ld long double

using namespace std;

const int N = 1e5 + 10;

int t, n, m;
int a[N],b[N];

bool check(int x)
{
    int k = n - x;
    for (int i = 0; i < x; i++)
    {
        if (a[i] >= b[i + k])
        {
            return false;
        }
    }
    return true;
}

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

    a[0] = 1;
    for (int i = 0; i < n; i++)cin >> b[i];

    sort(a, a + n);
    sort(b, b + n);

    
    int l = 0, r = n, mid=0;
    while (l<r)
    {
        mid = (l + r+1) >> 1;//mid为a保留mid位，即删去n-mid位
        if (check(mid))
        {
            l = mid;
        }
        else r = mid - 1;
    }
    cout << n - l << endl;
}

signed main()
{
    //t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }

    return 0;
}