2024年第十五屆藍橋杯C&C++大學A組--成績統計
題目：
動態規劃，
對于該題，考慮動態規劃解法，先取前k個人的成績計算其方差，并將成績記錄在數組中，記錄當前均值，設小藍已檢查前i-1個人的成績，若方差依然大于T，找出離均值最遠的一個成績，若第i個人的成績距離當前均值更近，則剔除離均值較遠的成績，使得方差變小，若遍歷完整個數組均找不到更小的方差，返回-1。
代碼：
#include<bits/stdc++.h>
using namespace std;
int n, k, T;
vector<int> nums;
vector<int> team;bool is0()
{double mean,val;double sum = 0;for (auto num : team){sum += num;}mean = sum / k;val = 0;for (auto num : team){val += (num - mean) * (num - mean);}val /= k;if (val < T) return true;else return false;
}int main()
{cin >> n >> k >> T;int N = n;while (N--){double temp;cin >> temp;nums.push_back(temp);}if (n < k){cout << -1;return 0;}double sum = 0;for (int i = 0;i < k; i++){team.push_back(nums[i]);sum += nums[i];}double mean = sum / k;if (is0()){cout << k;return 0;}for (int i = k; i < nums.size(); ++i){double sub = 0;int x = -1;for (int j = 0; j < team.size(); ++j){if (abs(team[j] - mean) > sub)//找出距離平均值最遠的值和下標{sub = abs(team[j] - mean);x = j;}}if (x != -1 && sub > abs(nums[i] - mean))team[x] = nums[i];if (is0()){cout << i + 1;return 0;}return -1;}return 0;
}
)
