【蓝桥杯】（C++）2024.9.22算法赛——你会二分吗？

你会二分吗？

题目

你会二分吗？

题目分析

1.用两个数组来存储男、女员工的e人值，对数组进行排序，然后男女员工两两配对，使得其最小值最大

for (int i = 0; i < n; i++)
{cin >> m[i];
}
for (int i = 0; i < n; i++)
{cin >> w[i];
}
sort(m, m + n);
sort(w, w + n);

 

int min = m[0] + w[0];
int max = m[n - 1] + w[n - 1];
int mid = (min + max) / 2;

2.采用二分法寻找这个最大的最小值，在二分搜索中用mid表示这个最大的最小值，然后检查是否存在一种配对方式，使得所有配对的e人值都不小于mid

while (mid<max && mid>min)//mid在min和max之间时循环 
{if (check(mid)){min = mid;mid = (mid + max) / 2;}else{max = mid;mid = (min + mid) / 2;}
}

3.使用贪心进行配对，从e人值最小的男员工和女员工开始配对，并检查他们的e人值之和是否大于mid。如果所找到的配对方式使得所有配对的e人值之和都大于或等于mid，那则增大mid值，否则减少mid值。

// 检查是否存在m[i] + w[j] >= x的组合，其中i从0开始，j从n-1开始递减
int check(int x)
{int j = n - 1;for (int i = 0; i < n; i++){if (m[i] + w[j--] < x){return 0;}}return 1;
}

代码（复杂版）

#include <iostream>
#include<algorithm>
using namespace std;int n;
int m[100000], w[100000];// 检查是否存在m[i] + w[j] >= x的组合，其中i从0开始，j从n-1开始递减
int check(int x)
{int j = n - 1;for (int i = 0; i < n; i++){if (m[i] + w[j--] < x){return 0;}}return 1;
}void fun()
{int min = m[0] + w[0];int max = m[n - 1] + w[n - 1];int mid = (min + max) / 2;while (mid<max && mid>min)//mid在min和max之间时循环 {if (check(mid)){min = mid;mid = (mid + max) / 2;}else{max = mid;mid = (min + mid) / 2;}}cout << min;
}int main()
{cin >> n;for (int i = 0; i < n; i++){cin >> m[i];}for (int i = 0; i < n; i++){cin >> w[i];}sort(m, m + n);sort(w, w + n);fun();return 0;
}

代码（简单版）

#include<iostream>
#include<algorithm>
using namespace std;bool com(int x, int y)
{return x > y;
}int main()
{int n;cin >> n;int m[100000], w[100000],c[100001];for (int i = 0; i < n; i++){cin >> m[i];}for (int i = 0; i < n; i++){cin >> w[i];}sort(m, m + n);//小到大排序sort(w, w + n, com);//大到小排序for (int i = 0; i < n; i++){c[i] = w[i] + m[i];}sort(c, c + n);cout << c[0];return 0;
}