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;
}
标签:905,int,mid,long,Codeforces,Dances,version,Easy
From: https://www.cnblogs.com/ikunhuaji/p/17783507.html