数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++程序：计算组队所需解决的最小问题数
假设我们有一个包含n个元素的数组A。大学里有n名学生，n为偶数。第i个学生的编程技能等于A[i]。团队领导想要组建n/2个团队。每个团队应该恰好包含两名学生，每个学生应该恰好属于一个团队。只有当两名学生的技能相等时，他们才能组成一个团队。学生可以解决问题来提高他们的技能。如果他们解决一个问题，他们的技能将增加1。我们必须找到学生应该解决的最小总问题数，以组建恰好n/2个团队。
问题类别
这个问题属于排序问题。在讨论计算机科学中不同的问题解决算法时，排序是一个非常常见的问题。顾名思义，排序表示将一组数据排列成某种方式。通常，我们可以按非递减顺序或非递增顺序排列它们。否则，排序也可以以预定义的方式进行。对于基于字符串的问题，有时我们使用词典排序来按字典顺序排列字母。有很多不同的排序技术，它们有一定的变化以及时间和空间复杂度。迄今为止，基于比较的排序技术的时间复杂度的下限是O(n*log n)。但是，也有一些机械排序技术，如桶排序、基数排序、计数排序，它们的时间复杂度是线性的O(n)。如需进一步阅读，请点击下面的链接：
https://tutorialspoint.com/data_structures_algorithms/sorting_algorithms.htm
因此，如果我们问题的输入类似于A = [5, 10, 2, 3, 14, 5]，则输出将为5，因为团队可以是(2,3)、(0,5)和(1,4)。然后，为了组成第一个团队，第三个学生应该解决1个问题，为了组成第二个团队，没有人需要解决问题，为了组成第三个团队，第二个学生应该解决4个问题。
步骤
为了解决这个问题，我们将遵循以下步骤：
n := size of A cnt := 0 sort the array A for initialize i := 0, when i < n, update i := i + 2, do: cnt := cnt + A[i + 1] - A[i] return cnt
示例
让我们看看下面的实现，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A){
int n = A.size();
int cnt = 0;
sort(A.begin(), A.end());
for (int i = 0; i < n; i += 2)
cnt += A[i + 1] - A[i];
return cnt;
}
int main(){
vector<int> A = { 5, 10, 2, 3, 14, 5 };
cout << solve(A) << endl;
}输入
{ 5, 10, 2, 3, 14, 5 }输出
5
更新于：2022年4月8日
293 次浏览
广告