POJ 3579 Median(二分查找+找到第k大的值)(二分实例详解)-白红宇

POJ 3579 Median(二分查找+找到第k大的值)(二分实例详解)

阅读量：5302 次

发布时间：2019-06-14

本文共 4683 字，大约阅读时间需要 15 分钟。

　　昨天写二分wa了一晚上,早上起来重写了一边,莫名奇妙的过了......

　　这个题与平常的二分有所不同,像最大化最小值这种二分,有时候满足cnt=m的条件有很多,从中找出最小的或最大的,而此题是找到第k大的值,当满足cnt=m时,即找到了解,

　　这题有个特别坑的地方: median是中位数的意思,因为这个我也wa了n次,所以进行以下判断:

if(m%2==0) m=m/2;        else m=m/2+1;

　　这个题我用的是upper_bound来查找,找到的是第一个大于a[i]+x的元素的地址,

　　　　所以在计算小于等于a[i]+x的个数时,cnt+=(upper_bound(a+i,a+n,a[i]+x)-(a+i))-1;(注意最后要减一)

　　　　对于二分的bi边界条件和循环终止条件还是不太清楚,有的写法可以过,有的写法就是过不了,要么陷入死循环,有么结果会莫名奇妙的与题目差一个1.由于我比较笨,所以只能列举以上下面几种例子来具体说明

　　　　对于用upper_bound来查找,正确的循环应该写成这样:

bool C(int x){    int cnt=0;    rep(i,0,n){        cnt+=(upper_bound(a+i,a+n,a[i]+x)-(a+i))-1;        }    return cnt>=m;}

while(ub>lb){            mid=(ub+lb)/2;            if(C(mid)) ub=mid;            else lb=mid+1;            }

　　　　注意返回的是cnt>=m;(说明当x=mid时,cnt等于m或者cnt>m,)令ub=mid,如果cnt=m,令ub=mid 以后,ub就满足了条件(因为此题cnt=m只有一组解),此后lb会一直增加,直至与ub相等,(如正确值是8,此时lb=4,ub=12,则 mid=8,此时C(mid)=m满足条件,ub=8,下次循环mid=6<8,lb=mid+1=7,再进入下一次循环,mid=7<8,此时lb=mid+1=8满足条件,跳出循环,输出lb或者ub,所以如果循环写成下面这个样子,也是可以过的:

while(ub-lb>1){            mid=(ub+lb)/2;            if(C(mid)) ub=mid;            else lb=mid;            }

注意返回值还是cnt>=m;在来看另外一种情况,

　　若正确值是8,此时lb=3,ub=11,则mid=7<8,lb=mid+1=8,下次循环mid=(8+11)/2=9>mid,ub=mid=9,下次循环

mid=(8+9)/2=8满足题意,此时ub=8(注意lb也等于8),跳出循环,

　　若正确值是8,此时lb=7,ub=20,则mid=13>8,ub=mid=13,下次循环mid=(13+7)/2=10,ub=mid=10,再下次循环mid=(10+7)/2=8,ub=mid(找到可行解).

//华丽的分割线

如果此处写成:

bool C(int x){    int cnt=0;    rep(i,0,n){        cnt+=(upper_bound(a+i,a+n,a[i]+x)-(a+i))-1;        }    return cnt<=m;}

while(ub>lb){            mid=(ub+lb)/2;            if(C(mid)) lb=mid;            else ub=mid-1;            }

则对于某些样例,会进入死循环.

若正确值是8,lb=0,ub=9,则mid=(9+0)/2=4<8,所以lb=mid=4,下次循环mid=(4+9)/2=6<8,lb=6,下次mid=(6+9)/2=7,lb=7,下次mid=8,lb=8,下次

mid=8,lb=8,由于是if(C(mid)) lb=mid;所以会进入死循环,ub=mid-1;一直没能起作用.

///我是分割线///

　　综上,用cnt>=m,ub=mid,cnt<m,lb=mid+1,来判断时,ub一开始会大于m,后来会一直减小到m,此时ub不变(为m),当lb<m时,mid会一直小余m,所以如果让

lb=mid+1,则lb一定会增加到m,

　　对于第二种满足的循环判断,ub一开始会大于m,后来会一直减小到m,此时ub不变(为m),当lb<m时,mid会一直小余m,所以如果让lb=mid,则lb一定会增加到m-1,由于终止条件是(ub-lb)<=1,所以不会陷入死循环,可以输出正确答案(ub);

　　对于第三种cnt<=m,lb=mid,cnt<m,ub=mid-1(不满足题意的判断),lb一开始小余m,后来会一直增加到m,此时lb不变,若此时ub>m,则ub会一直减小到m+1,之后

mid一直等于m( (m+m+1)/2) ,则会陷入死循环,对于某些样例可能一开始运气比较好,mid恰好等于m+1,此时ub=mid-1=m,只有这种特殊情况才不会陷入死循环

　　引用某个大虾的话来说:

第一种方法是用的是upper_bound，功能是在一段单调递增的序列中找到第一个大于目标元素的地址。用处是可以统计小于或等于value的元素有多少个（所以要减1）。该函数使用二分快速查找，时间性能log n。思路是对于某个确定的d，通过枚举第一个元素的下标来统计以这个元素为首的数对有多少个是满足a[j] - a[i] <= d 的，然后累加，从而计算出有多少个数对的差值是小于等于d的。记差值小于等于d的数对的个数关于d的函数为cnt(d)，该函数单调递减，故使用左开右闭区间进行二分查找。

第二种方法使用的是lower_bound，功能是在一段单调递增的序列中找到第一个大于或等于目标元素的地址。用处是可以统计小于value的元素有多少个。使用左闭右开区间

lower_bound这种我就不写了,详情请见

///分割线///

以下是AC代码

/** Created:     2016年04月02日 10时36分40秒 星期六* Author:      Akrusher**/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      #include 
                      
                       #include 
                       
                        #include 
                        
                         using namespace std;#define rep(i,a,n) for (int i=a;i
                         
                          =a;i--)#define in(n) scanf("%d",&(n))#define in2(x1,x2) scanf("%d%d",&(x1),&(x2))#define inll(n) scanf("%I64d",&(n))#define inll2(x1,x2) scanf("%I64d%I64d",&(x1),&(x2))#define inlld(n) scanf("%lld",&(n))#define inlld2(x1,x2) scanf("%lld%lld",&(x1),&(x2))#define inf(n) scanf("%f",&(n))#define inf2(x1,x2) scanf("%f%f",&(x1),&(x2))#define inlf(n) scanf("%lf",&(n))#define inlf2(x1,x2) scanf("%lf%lf",&(x1),&(x2))#define inc(str) scanf("%c",&(str))#define ins(str) scanf("%s",(str))#define out(x) printf("%d\n",(x))#define out2(x1,x2) printf("%d %d\n",(x1),(x2))#define outf(x) printf("%f\n",(x))#define outlf(x) printf("%lf\n",(x))#define outlf2(x1,x2) printf("%lf %lf\n",(x1),(x2));#define outll(x) printf("%I64d\n",(x))#define outlld(x) printf("%lld\n",(x))#define outc(str) printf("%c\n",(str))#define pb push_back#define mp make_pair#define fi first#define se second#define SZ(x) ((int)(x).size())#define mem(X,Y) memset(X,Y,sizeof(X));typedef vector
                          
                            vec;typedef long long ll;typedef pair
                           
                             P;const int dx[4]={ 1,0,-1,0},dy[4]={ 0,1,0,-1};const int INF=0x3f3f3f3f;const ll mod=1e9+7;ll powmod(ll a,ll b) {ll res=1;a%=mod;for(;b;b>>=1){ if(b&1)res=res*a%mod;a=a*a%mod;}return res;}const bool AC=true;int n,m;int a[100005];bool C(int x){ int cnt=0; rep(i,0,n){ cnt+=(upper_bound(a+i,a+n,a[i]+x)-(a+i))-1; } return cnt>=m;}int main() { int lb,ub,mid; while(in(n)!=EOF){ rep(i,0,n){ in(a[i]); } m=n*(n-1)/2; if(m%2==0) m=m/2; else m=m/2+1; //注意是中位数 sort(a,a+n); lb=0,ub=a[n-1]-a[0]; //lb最小值是0,ub赋值a[n-1]-a[0]肯定满足题意,当(n=1时也满足) while(ub>lb){ mid=(ub+lb)/2; if(C(mid)) ub=mid; else lb=mid+1; } out(ub); } return 0;}

转载于:https://www.cnblogs.com/akrusher/articles/5347380.html

你可能感兴趣的文章