本文主要是介绍week4 C - 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 非常想得到那只可爱的猫咪，你能帮帮他吗？
输入输出：
Input：多组输入，每次输入一个 N，表示有 N 个数，之后输入一个长度为 N 的序列 cat， cat[i] <= 1e9 , 3 <= n <= 1e5
output：输出新数组 ans 的中位数
解题思路：
给出一个数组，然后根据这个数组构造一个新数组，求这个新数组的中位数，这里利用了二分答案的思想，即最开始中位数会有一个区间，中位数一定位于这个区间内，二分到一个可能答案jiashe，求该答案的名次，如果该名次比中位数的名次小，就在jiashe+1到r这个区间找，反之，在l到jiashe区间找，一直利用二分过程，直到low>high，循环结束此时的jiashe就是最终要求的中位数。
首先看，怎么求一个数的名次，根据新数组的构建方式ans[] = abs(cat[i] - cat[j])，1 <= i < j <= N，可知，要知道这个数大于等于ans[]数组的多少数，对数组cat进行排序，问题转化为即jiashe≥cat[j] - cat[i]（1 <= i < j <= N） ，可以通过枚举i，二分j，即cat[j]<=cat[i]+jiashe，找到数组中最后一个<=cat[i]+jiashe的索引即可。为了避免不必要的搜索，优化剪枝，对于每一个jiashe，从数组中某个i开始，j从i+1到n-1会一直满足条件，所以先找到这个临界值，a[n-1]-a[i]<=jiashe，a[i]>=a[n-1]-jiashe，找到第一个大于该值的索引。问题转化为从i从0到这个临界值的枚举，然后二分搜索求j。
实验代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int a[100100]; int BinarySearch(int goal,int left,int right)
{int l=left,r=right;int mid,ans=left-1; while(l<=r){ mid=(r+l)/2; if(a[mid]>goal){r=mid-1; }else {ans=mid;l=mid+1;} }return (ans-left+1);
}
int BinarySearch_bigger(int goal,int left,int right)
{int l=left,r=right;int mid,ans=-1; while(l<=r){ mid=(r+l)/2; if(a[mid]<goal){l=mid+1; }else {ans=mid;r=mid-1; } }return ans;
}
int getAns(int n)
{long long int len=n*(n-1)/2; long long int ansless=(len+1)/2 ; int low=0,high=a[n-1]-a[0]; int jiashe;while(low<=high) { jiashe=(high+low)/2; //二分答案if(low==high) return jiashe; long long int mc=0;int end;if((end=BinarySearch_bigger(a[n-1]-jiashe,0,n-1))!=-1) //找临界值 mc+=(n-end)*(n-end-1)/2;else end=n-1;for(int i=0;i<end;i++) {if(a[i+1]-a[i]<=jiashe) mc+=BinarySearch(jiashe+a[i],i+1,n-1); }if(mc>=ansless) high=jiashe;else if(mc<ansless) low=jiashe+1;}
}
int main(void)
{int n;while(scanf("%d",&n)){//接下来要输入n个数 for(int i=0;i<n;i++)scanf("%d",&a[i]); //输入数据 sort(a,a+n);printf("%d\n",getAns(n));}return 0;
}
这篇关于week4 C - TT 的神秘礼物的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
