Visit Counter
AmazingCounters.com

1、感谢POPOQQQ, TKD, VFK
2、题目大意:就是给你三个数组啦,然后让你找到其中的第K大,但是,不可以直接访问数组,必须通过一种函数,最后的分数
是看调用几次这个函数,100次以内10分,2000以内6分。。。。
3、分析:最开始,并不会100分啦,所以就敲了一个六十分的代码,
就是二分一个值,然后再套一个二分验证一下,这样就过了60分(可还是憋了one hour)
代码:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <ctime>
#include <kth.h>
using namespace std;
int get_a_min(int na, int value){
    if(na == 0) return 0;
    int l = 0, r = na - 1;
    int odl = 0, odr = 0;
    while(l < r){
        int mid = (l + r) / 2;
        if(get_a(mid) > value) r = mid - 1;
        else l = mid;
        if(odl == l && odr == r) break;
        odl = l; odr = r;
    }
    if(get_a(r) <= value) return r + 1;
    else return l + 1;
}
int get_b_min(int nb, int value){
    if(nb == 0) return 0;
    int l = 0, r = nb - 1;
    int odl = 0, odr = 0;
    while(l < r){
        int mid = (l + r) / 2;
        if(get_b(mid) > value) r = mid - 1;
        else l = mid;
        if(odl == l && odr == r) break;
        odl = l; odr = r;
    }
    if(get_b(r) <= value) return r + 1;
    else return l + 1;
}
int get_c_min(int nc, int value){
    if(nc == 0) return 0;
    int l = 0, r = nc - 1;
    int odl = 0, odr = 0;
    while(l < r){
        int mid = (l + r) / 2;
        if(get_c(mid) > value) r = mid - 1;
        else l = mid;
        if(odl == l && odr == r) break;
        odl = l; odr = r;
    }
    if(get_c(r) <= value) return r + 1;
    else return l + 1;
}
int query_kth(int n_a, int n_b, int n_c, int k){
    int l = 0, r = max(max(get_a(n_a - 1), get_b(n_b - 1)), get_c(n_c - 1));
    int odl = 0, odr = 0;
    while(l < r){
        int mid = (l + r) / 2;
        int wt = get_a_min(n_a, mid) + get_b_min(n_b, mid) + get_c_min(n_c, mid);
        if(wt < k) l = mid;
        else r = mid;
        if(odl == l && odr == r) break;
        odl = l; odr = r;
    }
    int o1 = get_a_min(n_a, l) + get_b_min(n_b, l) + get_c_min(n_b, l);
    int o2 = get_a_min(n_a, r) + get_b_min(n_b, r) + get_c_min(n_b, r);
    if(o1 >= k) return l + 1;
    else return r;
}
    萌萌哒100分做法,就是我们把每个数组的第k/3个数求出来,然后就是选最小的那个数组,这个数组的前k/3个数都没有用了,我们就可以删掉,然后每次删删删,于是递归若干次,就可以100分了

代码:(缩了一下行,,,)

#include"kth.h"
#include<iostream>
using namespace std;
int query_kth(int n_a,int n_b,int n_c,int k){
    int ca=0,cb=0,cc=0;
    int t_min;
    while(k){
        int t=max(0,k/3-1); int ta=get_a(ca+t),tb=get_b(cb+t),tc=get_c(cc+t);
        t_min=min(ta,min(tb,tc));t++;
        if(t_min==ta)ca+=t; else if(t_min==tb)cb+=t; else cc+=t; k-=t;
    }
    return t_min;
}

4、分类:乱搞