题目描述
解题思路
对于该题,先取前k个人的成绩计算其方差,并将成绩记录在数组中,记录当前均值,设小蓝已检查前i-1个人的成绩,若方差依然大于T,找出离均值最远的一个成绩,若第i个人的成绩距离当前均值更近,则剔除离均值较远的成绩,使得方差变小,若遍历完整个数组均找不到更小的方差,返回-1
附代码
#include#include #include #define ll long long using namespace std; vector t; vector nums; int N, k, T; bool calculate0() { //判断方差是否小于指定值 double e; double sum = 0; for (auto num : t) { sum += num; } e = sum / k; double val = 0; for (auto num : t) { val += (num - e) * (num - e); } 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 mean = 0; for (int i = 0; i < k; i++) { t.push_back(nums[i]); mean += nums[i]; } mean /= k; if (calculate0()) { cout << k; return 0; } for (int length = k; length < nums.size(); length++) { double sub = 0; int x = -1; for (int i = 0; i < t.size(); i++) { if (abs(t[i] - mean) > sub) { sub = abs(t[i] - mean); x = i; } } if (x != -1 && sub > abs(nums[length] - mean)) //判断是否更接近均值 t[x] = nums[length]; if (calculate0()) { cout << length + 1; return 0; } } cout << -1; return 0; }