如何用长尾词策略解决codeforce-1201-C题，实现高效编程？
- 内容介绍
- 文章标签
- 相关推荐
本文共计941个文字，预计阅读时间需要4分钟。
题目：给你一个包含n个整数的数组A（n为奇数），对A进行以下k次操作：+ 对数组排序，使数组以非递减顺序排列。+ 选择数组的中位数，然后加一。+ 最终使得数组的中间数最大。+ 输入：第一行输入n k（用空格分隔）
题目：给你一个包含n个整数的数组A（n为奇数），对A做k次以下操作：
- 对数组排序使数组以非递减顺序排列。
- 选取数组的中位数，然后加一
最终使得数组的中位数最大。
输入：第一行输入两个数字 n 和 k ——数组大小和进行的操作次数
输出：输出最大中位数
栗子：输入 3 2
1 3 5
输出 5
（对于这个问题笔者刚开始想的按数组进行二分但是时间复杂度为O(kn)爆了所以更改思路按值进行二分）
思路：最大中值，那么计算结束数组应该满足--从中间开始到中间后i位的值相等且等于最大中位数。
首先定义一个的右值（右值应大于数组中的每一个元素，只要大于题目中给的1e9即可），求出其中位数。其次判断此中位数是否满足最大中位数的定义，若是，那么左值为此中位数（要求的是最大中位数）。若不是，那么右值为此中位数减一
check函数判断是否满足最大中位数的定义
bool check(ll mid) // 检查mid是否是真正的中值 { ll s = 0; for (int i = n / 2; i < n; i++) { if (mid > A[i]) // A[i] > mid A[i]是不进位的，因为就加不到A[i]那位 s = s + mid - A[i]; } return (s <= k); // 当s > k时，要成为mid所需要的数比给的数多，则加不到mid那位 所以此mid } // 不是中值 此mid大了 如果小点那么可能就是中值了
然后缩小范围找最大中值
while (l < r) { mid = (l + r + 1) / 2; if (check(mid)) // 当mid是中值的时候可以选并且继续求大于mid的值是否满中值 l = mid; else r = mid - 1; // mid不是中值的时候说明mid太大了，要往小的调 }
为什么mid = (l+r+1)/2？因为二分搜索一般用向下取整
详细请参考：www.cnblogs.com/flipped/p/4991658.html
完整代码：
#include <iostream> #include <algorithm> using namespace std; typedef long long ll; const int maxn = 200010; ll n, k, A[maxn]; bool check(ll mid) // 检查mid是否是真正的中值 { ll s = 0; for (int i = n / 2; i < n; i++) { if (mid > A[i]) // A[i] > mid A[i]是不进位的，因为就加不到A[i]那位 s += mid - A[i]; } return (s <= k); // 当s > k时，要成为mid所需要的数比给的数多，则加不到mid那位 所以此mid } // 不是中值 此mid大了 如果小点那么可能就是中值了 int main() { int i; ll l = 0, r = 3e9; ll mid; scanf_s("%lld%lld", &n, &k); for (i = 0; i < n; i++) scanf_s("%lld", &A[i]); sort(A, A + n); while (l < r) { mid = (l + r + 1) / 2; if (check(mid)) // 当mid是中值的时候可以选并且继续求大于mid的值是否满中值 l = mid; else r = mid - 1; // mid不是中值的时候说明mid太大了，要往小的调 } printf("%lld", l); return 0; }
笔者建议通过逐步运行加上计算的方法理解此题。
由于笔者才疏学浅，文中难免存在一些错误或疏漏，恳请读者批评指正。
本文共计941个文字，预计阅读时间需要4分钟。
题目：给你一个包含n个整数的数组A（n为奇数），对A进行以下k次操作：+ 对数组排序，使数组以非递减顺序排列。+ 选择数组的中位数，然后加一。+ 最终使得数组的中间数最大。+ 输入：第一行输入n k（用空格分隔）
题目：给你一个包含n个整数的数组A（n为奇数），对A做k次以下操作：
- 对数组排序使数组以非递减顺序排列。
- 选取数组的中位数，然后加一
最终使得数组的中位数最大。
输入：第一行输入两个数字 n 和 k ——数组大小和进行的操作次数
输出：输出最大中位数
栗子：输入 3 2
1 3 5
输出 5
（对于这个问题笔者刚开始想的按数组进行二分但是时间复杂度为O(kn)爆了所以更改思路按值进行二分）
思路：最大中值，那么计算结束数组应该满足--从中间开始到中间后i位的值相等且等于最大中位数。
首先定义一个的右值（右值应大于数组中的每一个元素，只要大于题目中给的1e9即可），求出其中位数。其次判断此中位数是否满足最大中位数的定义，若是，那么左值为此中位数（要求的是最大中位数）。若不是，那么右值为此中位数减一
check函数判断是否满足最大中位数的定义
bool check(ll mid) // 检查mid是否是真正的中值 { ll s = 0; for (int i = n / 2; i < n; i++) { if (mid > A[i]) // A[i] > mid A[i]是不进位的，因为就加不到A[i]那位 s = s + mid - A[i]; } return (s <= k); // 当s > k时，要成为mid所需要的数比给的数多，则加不到mid那位 所以此mid } // 不是中值 此mid大了 如果小点那么可能就是中值了
然后缩小范围找最大中值
while (l < r) { mid = (l + r + 1) / 2; if (check(mid)) // 当mid是中值的时候可以选并且继续求大于mid的值是否满中值 l = mid; else r = mid - 1; // mid不是中值的时候说明mid太大了，要往小的调 }
为什么mid = (l+r+1)/2？因为二分搜索一般用向下取整
详细请参考：www.cnblogs.com/flipped/p/4991658.html
完整代码：
#include <iostream> #include <algorithm> using namespace std; typedef long long ll; const int maxn = 200010; ll n, k, A[maxn]; bool check(ll mid) // 检查mid是否是真正的中值 { ll s = 0; for (int i = n / 2; i < n; i++) { if (mid > A[i]) // A[i] > mid A[i]是不进位的，因为就加不到A[i]那位 s += mid - A[i]; } return (s <= k); // 当s > k时，要成为mid所需要的数比给的数多，则加不到mid那位 所以此mid } // 不是中值 此mid大了 如果小点那么可能就是中值了 int main() { int i; ll l = 0, r = 3e9; ll mid; scanf_s("%lld%lld", &n, &k); for (i = 0; i < n; i++) scanf_s("%lld", &A[i]); sort(A, A + n); while (l < r) { mid = (l + r + 1) / 2; if (check(mid)) // 当mid是中值的时候可以选并且继续求大于mid的值是否满中值 l = mid; else r = mid - 1; // mid不是中值的时候说明mid太大了，要往小的调 } printf("%lld", l); return 0; }
笔者建议通过逐步运行加上计算的方法理解此题。
由于笔者才疏学浅，文中难免存在一些错误或疏漏，恳请读者批评指正。