21
2017
09

【转】【DBSDFZOJ 1163】分治 第K小元素(分治)

来源:Dilhao的博客

Description

输入n个整数和一个正整数k(1<=k<=n)输出这些整数从小到大排序后的第k个(例如,k=1就是最小值)。n<=2*10^6。

Input

第一行输入N和K(1<=K<=N<=2*10^6)。
接下来一行N个数描述序列。

Output

输出第K小的数。

Sample Input

5 3
2 1 2 6 3

Sample Output

2
看起来很简单是不是,只需要一个sort就解决了?
好吧,,,我们再来看看数据范围,,2*10^6,貌似nlog(n)过不去,这可怎么办呢,
那好吧,,既然排序不行的话,,没错,分治貌似是个好办法,一次通过O(n)的时间将元素简单的按大小分成两堆,然后我们一次就可以将问题规模缩小一半
我们规定一个数(在数组里面随便取,rand( )都没人管你)作为分类标准,将当前数组里比它大的数随意扔在一个数组里,将当前数组里比它小的数扔在另一个数组里,当然,我们还要记录一下和他大小相等的数的个数,然后我们观察,如果小数堆的size比k大的话,我们就去小数堆里面继续找我们想要的数,如果k比小数堆的size加上相同数的数量还大的话,那么我们就把k减去对应的size,然后去大数堆里继续找,
以为这样就可以A掉这道题?那你可真是天真,,,
这里写图片描述
没错,,生命在于尝试
我一开始看到这道题,从来没想到它会丧心病狂的卡我一下午的时间,,
可以说的是,纯分治是铁定过不去的
分治的思想是不断缩小问题规模,,
再好好想一想,,想到了什么?
没错!当问题规模缩小到一定程度时,大量重复的分治操作性价比反而不如排序
所以说,,我们只要当我们操作的数组元素小于100000时,我们就可以直接排序了,这样直接输出第k小元素,
脑洞被刷新了有没有,,有时候我们要综合算法的优点嘛
下面上代码,,,代码丑勿喷,,

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
using namespace std;
int n,k,num[4][2000005];
int l,r,ll,rr,now=0,ano=1;
int x,y;
int x1=1,x2=2,x0=0;//这里用了一点滚动数组的小技巧,x0,x1,x2分别是当前数组,小数堆,大数堆的数组下标 
int main()
{
    scanf("%d%d",&n,&k);  y=n;

    for(int i=1;i<=y;i++)  scanf("%d",&num[x0][i]);//输入原数组 

    while(y>0)//y是当前数组的大小 
    {
        if(y<=100005) //规模足够 直接排序 
        {
            sort(num[x0]+1,num[x0]+y+1); 
            printf("%d",num[x0][k]);
            return 0;
        }

        if(k==1) //优化,直接找最小的 
        {
            int ansl=2147483647;
            for(int i=1;i<=y;i++)
            {
                ansl=min(ansl,num[x0][i]);
            }printf("%d",ansl);
            return 0;
        }
        else if(k==y)  //直接找最大的 
        {
            int ansl=-2147483647;
            for(int i=1;i<=y;i++)
            {
                ansl=max(ansl,num[x0][i]);
            }printf("%d",ansl);
            return 0;
        }


        x=num[x0][y>>1];//随意取数作为分类标准 

        int y0=0,y1=0,y2=0;//y0,y1,y2分别记录了相同数的个数,小数个数,大数个数 

        for(int i=1;i<=y;i++)
        {
            if(num[x0][i]==x)       y0++;//记录相同数个数 
            else if(num[x0][i]<x)   num[x1][++y1]=num[x0][i];//记录小数 
            else                    num[x2][++y2]=num[x0][i];//记录大数 
        }

        if(y1+y0<k)      {y=y2;    k-=(y1+y0);   swap(x0,x2);}//挑大数堆 交换下标 继续 

        else if(k<=y1)   {y=y1;                  swap(x0,x1);}//挑小数堆 交换下标 继续

        else             {printf("%d",x);     return 0;}//正好第k个 输出 
    }

    return 0;
}
上一篇:Solr控制台索引维护-删除索引 下一篇:输入一个int型整数,按照从右向左的阅读顺序,返回一个不含重复数字的新的整数。