1、两两配对差值最小
题目描述：给定一个长度为偶数的数组arr，将该数组中的数字两两配对并求和，在这些和中选出最大和最小值，请问该如何两两配对，才能让最大值和最小值的差值最小？
分析： 主要是利用了c++里面对数组的一个排序函数sort(数组名，数组名 + 数组长度）。使用这个函数需要导入#include求两两配对差值最小，其实就是把输入的数字排排序之后，从中间两位开始求和，再从中间向外面拓展一次求和，然后把求和的结果存到一个数组，再对这个数组排序，求最大最小值之差就可。
int find(vector<int>arr)
int n=arr.size();
sort(arr,arr+n); // 升序排序
int max=INT_MIN;
int min=INT_MAX;
for(int i = 0 ;i<(n/2);i++){
max = max(max, arr[i]+arr[n-i-1]);
min = min(min, arr[i]+arr[n-i-1]);
}
return max-min;
}
2、两两配对完成任务
题目描述： 小Q有M(M为偶数)名员工, 第i名员工完成工作的时候有一个拖延时间值ti。现在小Q手里有M/2份工作需要完成, 每一份工作都需要安排两名员工参与, 对于第i份工作所需完成的时间为两名员工的拖延时间值总和。现在M/2份工作同时开始进行,小Q希望所有工作结束的时间尽量早, 请你帮小Q设计一个优秀的员工分配方案,使得用尽量少的时间完成所有工作,并输出工作所需的最短时间。
输入描述：第一行为一个正整数n(1<=n<=105)。接下来有n行，每行两个正整数x和y，表示有x名员工的拖延时间值为y(1<=y<=109)。保证所有x的总和等于M(2<=M<=109), 保证M为偶数。
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
struct node {
int x; //x名员工
int y; //该x名员工的拖延时间都为y
};
bool cmp(node a, node b) {
return a.y < b.y;
}
int main() {
int n;
cin >> n;
vector<node> nums(n);
for (int i = 0; i < n; i++) {
cin >> nums[i].x;
cin >> nums[i].y;
}
//按照时间消耗大小进行排序
sort(nums.begin(), nums.end(), cmp);
/*
1.利用贪心算法
最大时间和最小时间的进行组合
次大消耗时间的和次小时间的进行组合
2.保证每两个员工完成同一份工作
*/
int left = 0;
int right = n - 1;
int res = 0;
while (left <= right) {
//记录nums[left]和nums[right]之中最少的员工数
int number = min(nums[left].x, nums[right].x);
//如果left和right 指向了同一组，number必须减半
//因为nums[left].x和nums[right].x 都要消耗一半
if (left == right) {
number /= 2;
}
//计算最少需要的工作时间
res = max(res, nums[left].y + nums[right].y);
//更新nums[left]和nums[right]中剩余的可用员工
nums[left].x -= number;
nums[right].x -= number;
//如果可以用的员工变为0了 更新left和right
if (nums[left].x == 0) left++;
if (nums[right].x == 0) right--;
}
cout << res << endl;
system("pause");
return 0;
}
