这一题我快做出阴影了，当然题目不好做，我看了别人的讲解才做出来，但是自己实现的时候各种狗屁错误，我tm。。。
本题做法： E(k)：表示可以redip k次的最优期望。 E(0) = sum(Vi) / N E(k): 如果取出的v > E(k-1)，那么留下；否则redip。 转移方程为：E(k) = (smallerCount * E(k-1) + largerSum) / N;这里的small large是相对于dp[k-1]说的。 所以这里要使用二分查找，而且的话使用前缀和来很快地知道大于部分的和。
#include <iostream> #include <vector> #include <algorithm> #include <cstdio> using namespace std; double helper(vector<int>& nums, int K); int main() { int T; cin >> T; int cnt = 0; while (++cnt <= T) { int N, K; cin >> N >> K; vector<int> nums; int num; while (N-- > 0) { cin >> num; nums.push_back(num); } double res = helper(nums, K); //cout << "Case #" << cnt << ": " << res << endl; printf("Case #%d: %f\n", cnt, res); } } double helper(vector<int>& nums, int K) { int sz = nums.size(); vector<double> dp(K+1, 0.0);//注意是K的大小 sort(nums.begin(), nums.end()); vector<long long> sums(sz, 0); sums[sz-1] = nums[sz-1]; for (int i = sz-2; i >= 0; --i) sums[i] = sums[i+1] + nums[i]; dp[0] = ((double)sums[0]) / sz; for (int i = 1; i <= K; ++i) { auto iter = upper_bound(nums.begin(), nums.end(), dp[i-1]); int cnt = iter - nums.begin(); dp[i] = (cnt*dp[i-1] + (cnt == sz ? 0 : sums[cnt])) / sz; }//注意cnt超出范围，在尾后的位置的情况 return dp.back(); }解法简单明了，但是自己实现的时候各种错误（比如dp的大小一开始设置为了sz等等），需要之后一直注意的几个问题有： 1.可以使用upper_bound, lower_bound, 以及binary search 来进行二分查找，含义和map的函数是一样的（https://www.cnblogs.com/Tang-tangt/p/9291018.html）。但是需要注意的一点是：upper_bound, lower_bound，它们返回的位置可能是尾后的位置，所以数组可能会越界。我一开始就是犯了这个错误，导致卡住，而且这种越界的错误最难排查，累死我了。 2.如果容器底层是连续内存的话，可以使用迭代器加减。 3.另外，对于kickstart，如果输出的是小数，那么就得用printf(#include < cstdio >)。可以看我注释掉的那一行，用cout输出就是错的，用printf就是对的，即使没有保留几位小数，但还是有用。
今天一晚上做了一题，我真的是fuck了。但是也收获不少吧，更多的是感觉ks好像没我想象的那么难，确实比平时lc做的要难，但是也有意思很多，也不是自己想不出来的那种，无非是：1.这种题目不熟悉2.这里码代码和lc上不太一样，不太适应。自己熟悉和适应之后是可以独立完成的ks的。
