本文主要是介绍D2. Dances (Hard Version) Codeforces Round 905 (Div. 2)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Problem - D2 - Codeforces
题目大意：有两个长度为n的数组a，b，给出一个数m，每次操作要删除a和b中的一个数然后将a,b按任意顺序排序，要求用最小的操作次数使对于任意的i都有a[i]<b[i]，求a[1]=1~m时最小操作次数的和。
2<=n<=1e5.1<=m<=1e9;1<=a[i],b[i]<=1e9
思路：首先考察每次操作的最优策略是什么，首先数字顺序肯定两个数组都要最小到大排序，要让a小于b，那么应该优先删除a中最大的数和b中最小的数，要删除多少数可以从1到n二分枚举，因为删除更多的数肯定更容易满足条件，符合单调性，这样我们就得到了a[1]固定为某个数时的答案。
我们令a[1]=1时的答案为ans，在我们增大a[1]到m的过程中，可以发现区别就是可能之前a[1]不用删，增大后要删，那么答案相差就是0或1，且操作次数是随着a[1]增大而增加的，所以我们可以二分枚举1到m找到答案+1的位置，也就是找到一个x使得a[1]=x时得到的答案与ans不同，这样前边的数量*ans后边的数量*(ans+1)就是最终的答案。
//#include<__msvc_all_public_headers.hpp>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const int N = 1e5 + 5;
ll n;
int a[N];
int temp[N];
int b[N];
bool check(int x)
{for (int i = 1; i <= n - x; i++){if (a[i] >= b[x + i]){//a中的前n-x个数和b中后n-x个数做对比return 0;}}return 1;
}
void init()
{}
void solve()
{cin >> n;int m;cin >> m;init();a[1] = 1;for (int i = 2; i <= n; i++){cin >> a[i];temp[i] = a[i];//复制一份a数组}for (int i = 1; i <= n; i++){cin >> b[i];}sort(a + 1, a + n + 1);sort(b + 1, b + n + 1);//将a和b按从小到大的顺序排序int l = 0, r = n, mid;ll ans;while (l <= r){//从1到n二分枚举操作次数mid = (l + r) >> 1;if (check(mid)){ans = mid;r = mid - 1;}else{l = mid + 1;}}l = 1, r = m;ll ans2 = m + 1;//初始化为m+1，没有枚举到答案不同的地方时，答案就是ans*mwhile (l <= r){//二分枚举a[1]，找到操作次数改变的第一个位置for (int i = 1; i <= n; i++){a[i] = temp[i];}mid = (l + r) >> 1;a[1] = mid;sort(a + 1, a + n + 1);if (!check(ans)){ans2 = mid;r = mid - 1;}else{l = mid + 1;}}cout << (ans2-1)*ans+(m-ans2+1)*(ans+1);//两个操作次数分别乘以他们的数量cout << '\n';
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);int t;cin >> t;//t = 1;while (t--){solve();}return 0;
}这篇关于D2. Dances (Hard Version) Codeforces Round 905 (Div. 2)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
