資料結構
網路
關係資料庫管理系統 (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.tw/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 次瀏覽
廣告