问题 L: 【分治】第k小整数II

你的忏悔或许会让你心安，但未必别人如此。

题目描述

“哇！好多冰淇淋啊！”张琪曼拉着李旭林又跑到学院的冷饮店，问：“老板，这次你要第k小魔法石？”老板笑着说：“我要……咦，你们实现把魔法石都排好了？那可不行，这不赖皮嘛，我要改下规则。”
老板的新规则是：对于两个有序数组a[n]和a[m]（1<n,m<100000），找出第k小的数。

输入

第一行三个整数n、m、k。
第二行是第一个有序数组的n个元素。
第三行是第二个有序数组的m个元素。

输出

两个数组中第k小整数值。

样例输入

复制样例数据

6 7 6
786 3891 4258 4694 7130 7899
357 720 1292 2579 7889 9255 9611

样例输出

3891

分治法：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <ctime>
#include <cctype>
#include <bitset>
#include <utility>
#include <sstream>
#include <complex>
#include <iomanip>
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
int s[100010],ss[100010],M,N,K;
int fd(int *s1,int cd1,int *s2,int cd2,int k){
    if(cd1>cd2)
        return fd(s2,cd2,s1,cd1,k);
    if(cd1==0)
        return s2[k-1];
    if(k==1)
        return min(s1[0],s2[0]);
    int k1=min(k/2,cd1);
    int k2=k-k1;
    if(s1[k1-1]>s2[k2-1])
        return fd(s1,cd1,s2+k2,cd2-k2,k-k2);
    else if(s1[k1-1]<s2[k2-1])
        return fd(s1+k1,cd1-k1,s2,cd2,k-k1);
    else
        return s1[k1-1];
}
int main(){
    scanf("%d%d%d",&N,&M,&K);
    for(int i=0;i<N;i++)
        scanf("%d",&s[i]);
    for(int i=0;i<M;i++)
        scanf("%d",&ss[i]);
    int jg=fd(s,N,ss,M,K);
    printf("%dn",jg);
    return 0;
}

这里提醒一下，元素相同也是要排到里面的，要不然答案就不对了。

最后

以上就是勤恳洋葱为你收集整理的问题 L: 【分治】第k小整数II的全部内容，希望文章能够帮你解决问题 L: 【分治】第k小整数II所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。