fork(1) download
  1. #include <iostream>
  2. #include <sstream>
  3. #include <vector>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. // 分治法:找出 arr[left...right] 區間的最小值與最大值
  8. pair<int, int> findMinMax(const vector<int>& arr, int left, int right) {
  9. // 若只有一個元素
  10. if (left == right) {
  11. return {arr[left], arr[left]};
  12. }
  13. // 若只有兩個元素,直接比較
  14. if (right - left == 1) {
  15. if (arr[left] < arr[right])
  16. return {arr[left], arr[right]};
  17. else
  18. return {arr[right], arr[left]};
  19. }
  20.  
  21. // 將陣列分成兩半
  22. int mid = left + (right - left) / 2;
  23. auto leftPair = findMinMax(arr, left, mid);
  24. auto rightPair = findMinMax(arr, mid + 1, right);
  25.  
  26. // 合併左右兩邊的結果
  27. int overallMin = min(leftPair.first, rightPair.first);
  28. int overallMax = max(leftPair.second, rightPair.second);
  29. return {overallMin, overallMax};
  30. }
  31.  
  32. int main() {
  33. // 讀取一行輸入
  34. string line;
  35. getline(cin, line);
  36. istringstream iss(line);
  37. vector<int> arr;
  38. int num;
  39. while (iss >> num) {
  40. arr.push_back(num);
  41. }
  42.  
  43. if (arr.empty()) {
  44. cout << "No input provided." << endl;
  45. return 0;
  46. }
  47.  
  48. // 使用分治法求最小值與最大值
  49. auto result = findMinMax(arr, 0, arr.size() - 1);
  50. int minVal = result.first;
  51. int maxVal = result.second;
  52.  
  53. // 輸出最大值與最小值的差值
  54. cout << (maxVal - minVal) << endl;
  55.  
  56. return 0;
  57. }
  58.  
Success #stdin #stdout 0.01s 5284KB
stdin
3
1 3 2 3 1 2
stdout
0