Week4 作业C TT的神秘礼物 二分答案 尺取

题意：

有n个数的数组cat（3<=n<=10^5，cat[i]<=10^9）,构造一个新的数组ans，ans[]=abs(cat[i]-cat[j])（i!=j），试求出这个新数组的中位数，中位数为排序后pos=(len+1)/2位置的数。

题目分析：

最直接的方法是将ans数组求出来然后排序，复杂度为O(n^2)，无法接受。

二分枚举答案，共有logn种答案。对于每一种答案p，求出p在数组ans中的最高名次f1(p)、最低名次f2(p)。若f1(p)<pos，说明答案p太小，转而二分枚举后半部分的答案；若f2(p)>pos，说明答案p太大，转而二分枚举前半部分的答案；否则，p为中位数。

只需讨论求最高名次f1(p)，最低名次f2(p)=f1(p-1)+1。为了去掉绝对值，对cat数组排序，则可以通过cat[j]-cat[i](i<j)求得ans中一半的数。所有满足cat[j]-cat[i]<=p的（i,j）数对的个数的2倍即为f1(p)。移项可得cat[j]<=cat[i]+p，cat有序，依然可以二分枚举。对于n个i，二分枚举j，求出满足条件的（i,j）数对的个数。复杂度为O(nlogn)，整体的复杂度为。

如果TLE，可以利用尺取法降成。当求出i=0时满足条件的j的最大位置cur时，i向后移动一个位置，cur向后移动的位置是有限的，并且i移动n个位置的过程，cur最多只移动n个位置。尺取法使用两个指针，只遍历一遍，求名次的过程复杂度为，整体过程为。

代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1e5+5;
const int maxx=1e9;
int n;
int cat[maxn];
int findLast(int x){//找到<=x的最右端位置 int l=0,r=n-1,ans=-1;while(l<=r){int mid=(l+r)>>1;if(cat[mid]<=x){ans=mid;l=mid+1;}else r=mid-1;}return ans;
}
//O(n)
int funcMax(int x)//求最高名次 从1开始 
{int ans=0;int cur=findLast(cat[0]+x);//findLast指针 int num=cur-0;ans+=num*2;for(int i=1;i<n;i++){ if(cur!=n-1){while(cur<=n-1 && cat[cur]<=cat[i]+x) cur++;cur--;}num=cur-i;ans+=num*2;}return ans; 
}
//O(nlogn)
int funcMax2(int x)//求最高名次 从1开始 
{int ans=0;int tmp=0;for(int i=0;i<n;i++){tmp=findLast(cat[i]+x)-i;tmp*=2;//交换i,j ans+=tmp;}return ans; 
}
int funcMin(int x)//求最低名次 从1开始
{return funcMax(x-1)+1;
} 
int solve()
{int len=n*n-n;int l=0 , r=maxx , ans=-1;while(l<=r){int mid=(l+r)>>1;int left=funcMin(mid) , right=funcMax(mid);if(right>=(len+1)/2 && left<=(len+1)/2){ans=mid ; break;} else if(right<(len+1)/2) l=mid+1;else if(left>(len+1)/2) r=mid-1;}  return ans;
}
int main()
{while(scanf("%d",&n)!=EOF){for(int i=0;i<n;i++) scanf("%d",&cat[i]);sort(cat,cat+n);printf("%d\n",solve());} return 0;
}