Week4:TT的神秘礼物——二分法求中位数

题目内容
TT 是一位重度爱猫人士,每日沉溺于 B 站上的猫咪频道。

有一天,TT 的好友 ZJM 决定交给 TT 一个难题,如果 TT 能够解决这个难题,ZJM 就会买一只可爱猫咪送给 TT。

任务内容是,给定一个 N 个数的数组 cat[i],并用这个数组生成一个新数组 ans[i]。新数组定义为对于任意的 i, j 且 i != j,均有 ans[] = abs(cat[i] - cat[j]),1 <= i < j <= N。试求出这个新数组的中位数,中位数即为排序之后 (len+1)/2 位置对应的数字,’/’ 为下取整。

TT 非常想得到那只可爱的猫咪,你能帮帮他吗?

输入格式
多组输入,每次输入一个 N,表示有 N 个数,之后输入一个长度为 N 的序列 cat, cat[i] <= 1e9 , 3 <= n <= 1e5。

输出格式
输出新数组 ans 的中位数。

输入示例

4
1 3 2 4
3
1 10 2

输出示例

1
8

解题思路
显然如果我是TT的话我就会放弃这只猫。
哎,中位数嘛,如果能把n的范围缩小一点那这道题将可以直接暴力算法绝杀,可惜换不得。

所以怎么二分呢?
对于一串数字,我们在已知这串数字的数量n的情况下,可以很容易地求得其中位数所在的位置为(n+1)>>1。

那么如果我们反着来看呢?
很明显我们即便不把ans数组直接算出来,也可以提前预判到其中位数所在的位置应该是((n * (n - 1)) / 2 + 1) / 2,此处n为cat数组的大小。

因此我们就可以继续分析:
已知了中位数的位置,我们只需要对ans进行二分:
那么对于某一个ans中的数P,
只需要求出小于等于它的数的个数就行了,这个个数如果等于中位数应该拥有的个数,那就说明P是中位数。
当然了,如果P比中位数少或者多,所以二分就行了。

但是既然用到了二分,那么我们就需要必要条件:被二分的数组应该是单调的。
看看题目:ans[] = abs(cat[i] - cat[j])
我们如何才能把绝对值化掉呢?
显然只需要保证cat[i]大于cat[j]就可以了。
我们可以提前对cat进行排列,然后保证i大于j就行了。
因此此时的式子变成了:P>=cat[i]-cat[j],其中i>j。
把cat[j]挪到式子左边:P+cat[j]>=cat[i]。
对于某个二分出来的P,我们只需要固定j,然后二分i就行了,这样就可以求出所有满足此式子的i和j的对数,即ans数组里小于等于P的数的个数。
复杂度为O(logk+nlogn),可以接受。

于是有代码:

#include <iostream>
#include <algorithm>
#include <vector>
#include <algorithm>using namespace std;vector<int>cat;
int n;bool cmp(const int& a, const int& b)
{return a < b;
}int Fun(int &mid,const int &rank)
{int currank = 0;for (int i = 0; i < n; i++){int temp = cat[i] + mid;int l = 0, r = n - 1, ans = -1;while (l <= r){int mid2 = (l + r) >> 1;if (cat[mid2] <= temp)//符合cat[j]+cat[i]<=P{ans = mid2;l = mid2 + 1;}else r = mid2 - 1;}if (ans != -1) currank += ans - i;}if (currank < rank) return 1;//小于if (currank >= rank) return 2;//大于等于
}int main()
{ios::sync_with_stdio(false);cin.tie(0);while (cin >> n){cat.clear();for (int i = 0; i < n; i++){int temp;cin >> temp;cat.push_back(temp);}sort(cat.begin(), cat.end(), cmp);int rank = ((n * (n - 1)) / 2 + 1) / 2;//中位数的名次int l = 0, r = cat.back() - cat.front(),ans=-1;while (l <= r){int mid = (l + r) >> 1;int opnum = Fun(mid, rank);if (opnum == 2){ans = mid;r = mid - 1;}else if (opnum == 1){l = mid + 1;}}if (ans != -1) cout << ans << endl;}
}

如果使用iostream,显然不要忘记使用

ios::sync_with_stdio(false);
cin.tie(0);

血的教训

Week4:TT的神秘礼物——二分法求中位数

题目内容
TT 是一位重度爱猫人士,每日沉溺于 B 站上的猫咪频道。

有一天,TT 的好友 ZJM 决定交给 TT 一个难题,如果 TT 能够解决这个难题,ZJM 就会买一只可爱猫咪送给 TT。

任务内容是,给定一个 N 个数的数组 cat[i],并用这个数组生成一个新数组 ans[i]。新数组定义为对于任意的 i, j 且 i != j,均有 ans[] = abs(cat[i] - cat[j]),1 <= i < j <= N。试求出这个新数组的中位数,中位数即为排序之后 (len+1)/2 位置对应的数字,’/’ 为下取整。

TT 非常想得到那只可爱的猫咪,你能帮帮他吗?

输入格式
多组输入,每次输入一个 N,表示有 N 个数,之后输入一个长度为 N 的序列 cat, cat[i] <= 1e9 , 3 <= n <= 1e5。

输出格式
输出新数组 ans 的中位数。

输入示例

4
1 3 2 4
3
1 10 2

输出示例

1
8

解题思路
显然如果我是TT的话我就会放弃这只猫。
哎,中位数嘛,如果能把n的范围缩小一点那这道题将可以直接暴力算法绝杀,可惜换不得。

所以怎么二分呢?
对于一串数字,我们在已知这串数字的数量n的情况下,可以很容易地求得其中位数所在的位置为(n+1)>>1。

那么如果我们反着来看呢?
很明显我们即便不把ans数组直接算出来,也可以提前预判到其中位数所在的位置应该是((n * (n - 1)) / 2 + 1) / 2,此处n为cat数组的大小。

因此我们就可以继续分析:
已知了中位数的位置,我们只需要对ans进行二分:
那么对于某一个ans中的数P,
只需要求出小于等于它的数的个数就行了,这个个数如果等于中位数应该拥有的个数,那就说明P是中位数。
当然了,如果P比中位数少或者多,所以二分就行了。

但是既然用到了二分,那么我们就需要必要条件:被二分的数组应该是单调的。
看看题目:ans[] = abs(cat[i] - cat[j])
我们如何才能把绝对值化掉呢?
显然只需要保证cat[i]大于cat[j]就可以了。
我们可以提前对cat进行排列,然后保证i大于j就行了。
因此此时的式子变成了:P>=cat[i]-cat[j],其中i>j。
把cat[j]挪到式子左边:P+cat[j]>=cat[i]。
对于某个二分出来的P,我们只需要固定j,然后二分i就行了,这样就可以求出所有满足此式子的i和j的对数,即ans数组里小于等于P的数的个数。
复杂度为O(logk+nlogn),可以接受。

于是有代码:

#include <iostream>
#include <algorithm>
#include <vector>
#include <algorithm>using namespace std;vector<int>cat;
int n;bool cmp(const int& a, const int& b)
{return a < b;
}int Fun(int &mid,const int &rank)
{int currank = 0;for (int i = 0; i < n; i++){int temp = cat[i] + mid;int l = 0, r = n - 1, ans = -1;while (l <= r){int mid2 = (l + r) >> 1;if (cat[mid2] <= temp)//符合cat[j]+cat[i]<=P{ans = mid2;l = mid2 + 1;}else r = mid2 - 1;}if (ans != -1) currank += ans - i;}if (currank < rank) return 1;//小于if (currank >= rank) return 2;//大于等于
}int main()
{ios::sync_with_stdio(false);cin.tie(0);while (cin >> n){cat.clear();for (int i = 0; i < n; i++){int temp;cin >> temp;cat.push_back(temp);}sort(cat.begin(), cat.end(), cmp);int rank = ((n * (n - 1)) / 2 + 1) / 2;//中位数的名次int l = 0, r = cat.back() - cat.front(),ans=-1;while (l <= r){int mid = (l + r) >> 1;int opnum = Fun(mid, rank);if (opnum == 2){ans = mid;r = mid - 1;}else if (opnum == 1){l = mid + 1;}}if (ans != -1) cout << ans << endl;}
}

如果使用iostream,显然不要忘记使用

ios::sync_with_stdio(false);
cin.tie(0);

血的教训