江苏省建设工人考勤网站,wordpress菜单链接关系,什么类型的网站比较容易做,那些网站可以做宣传题目描述 有一个老板有一袋金块。每个月将有两名雇员会因其优异的表现分别被奖励一个金块。按规矩#xff0c;排名第一的雇员将得到袋中最重的金块#xff0c;排名第二的雇员将得到袋中最轻的金块。根据这种方式#xff0c;除非有新的金块加入袋中#xff0c;否则第一名雇员…题目描述 有一个老板有一袋金块。每个月将有两名雇员会因其优异的表现分别被奖励一个金块。按规矩排名第一的雇员将得到袋中最重的金块排名第二的雇员将得到袋中最轻的金块。根据这种方式除非有新的金块加入袋中否则第一名雇员所得到的金块总是比第二名雇员所得到的金块重。如果有新的金块周期性的加入袋中则每个月都必须找出最轻和最重的金块。假设有一台比较重量的仪器我们希望用最少的比较次数找出最轻和最重的金块。
本题要求用二分算法完成。
输入 输入数据有多行第一行为金块个数n(2n5000000)接下来n行是n个金块的重量。
输出 输出最重的金块和最轻的金块用空格隔开。
样例输入
8
10
8
2
4
5
3
9
1
样例输出
10 1
问题分析 问题分解 将金块数组分为两半每一半分别寻找最重和最轻的金块。如果数组只剩下一个金块那么这个金块既是最重的也是最轻的。如果数组剩下两个金块通过简单比较即可确定哪个更重哪个更轻。 递归处理 递归地应用同样的过程到每一半的金块上直到只剩下一个或两个金块为止。这样的递归调用会持续地将问题规模减半直至达到可以直接解决的简单情况。 合并结果 在每个递归级别将两半金块的结果合并起来。对于每一对递归调用的结果比较并确定这两部分中的最重金块和最轻金块。最终顶层的递归调用将返回整个数组中的最重金块和最轻金块。
#include bits/stdc.h
using namespace std;// fz 函数用于找出数组中的最大值和最小值
// 它接收金块数组 a 以及当前搜索的范围 [l, r]
pairint,int fz(vectorint a, int l, int r) {if (l r) {// 如果只剩下一个元素那么这个元素既是最大值也是最小值return {a[l], a[r]};} else if (l 1 r) {// 如果只剩下两个元素比较这两个元素分别确定最大值和最小值return {max(a[l], a[r]), min(a[l], a[r])};}// 计算中间位置将数组分为两部分int mid r (l - r) / 2;// 递归地在左半部分找出最大值和最小值pairint, int left fz(a, l, mid);// 递归地在右半部分找出最大值和最小值pairint, int right fz(a, mid 1, r);// 比较左右两部分找到的最大值和最小值返回整体的最大值和最小值return {max(left.first, right.first), min(left.second, right.second)};
}int main() {int n; // 存储金块的数量cin n;vectorint a(n); // 使用一个向量来存储金块的重量// 读取金块的重量for (int i 0; i n; i) {cin a[i];}// 调用 fz 函数找出最重和最轻的金块pairint, int ans fz(a, 0, n - 1);// 输出最重的金块和最轻的金块cout ans.first ans.second endl;
}
