题目链接：https://uoj.ac/problem/52

做法

题解做法不难想到，每次把 $K$ 均摊到三个数组，查询三次，最小的那个数字显然一定在 $\le K$ 的范围内。

操作次数：$n\log_{\frac{n}{n-1}}{K}$ 左右。

但是这个做法存在优化的空间：

  1. 我们每次查询三个数组位置的和为 $K$ ，这个限制太强了，可以考虑放宽这个限制。
  2. 我们只利用到了最小的数字一定在 $\le K$ 的性质，没有利用到 最大的数字一定在 $\ge K$ 的性质。（但是上面那个做法每个数组查询的位置非严格单调递减，所以上面那个算法无法利用该性质进行优化。）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<bits/stdc++.h>
#include"kth.h"
using namespace std;
int cnt[3],ff[3],fucknow[3];
int getans(int x,int type){
    if(type==0)return get_a(x);
    else if(type==1)return get_b(x);
    else return get_c(x);
}
int lastans=0;
int solve1(int k){
    while(k){
        int pre=-1,preval=0;
        for(int i=0;i<=2;i++){
            if(cnt[i]<ff[i]){
                int now=getans(cnt[i],i);
                if(pre==-1 || now<preval)preval=now,pre=i;
            }
        }
        cnt[pre]++;k--;
        lastans=preval;
    }
    return lastans;
}
int id[10];
bool cmp(int x,int y){return (ff[x]-cnt[x])>(ff[y]-cnt[y]);}
int solve2(int k){
    for(int i=0;i<=2;i++)id[i]=i;
    while(k>2){
        int now=k;
        sort(id,id+3,cmp);
        for(int i=2;i>=0;i--){
            int x=id[i],s=min(ff[x]-cnt[x],now/(i+1));
            now-=s;fucknow[x]=cnt[x]+s;
        }
        int pre=-1,preval=0;
        for(int i=0;i<=2;i++){
            if(cnt[i]==ff[i])continue;
            int now=getans(fucknow[i]-1,i);
            if(pre==-1 || preval>now)preval=now,pre=i;
        }
        k-=fucknow[pre]-cnt[pre];cnt[pre]=fucknow[pre];
        lastans=preval;
        // printf("%d\n",k);
    }
    return solve1(k);
}
int query_kth(int n_a, int n_b, int n_c, int k){
    ff[0]=n_a;ff[1]=n_b;ff[2]=n_c;
    return solve2(k);
}

基于二分的做法：

接下来阐释做法时默认数字不同，相同的情况加个浮动可以转化为不同的情况。

每个数组都有个 $[L,R]$ ,考虑查询每个数组的 $mid$ ，$mid$ 总和为 $sum$ ， $sum\ge sum$ ，那么最大的数字一定在 $\ge sum$ 的位置。

$<sum$ ，那么最小的位置一定在 $<sum$ 的位置。

然后二分就行了。

最后把所有 $\ge K$ 的数字拉出来跑个最小值就行了。（不用搜索次数，之前自动记录）

至于为什么是对的？

证明：

首先，最后每个数字都会分为两类 $<K,\ge K$ ，那么显然 $\ge K$ 的数字中最小的那个就是 $=K$ 的数字，证毕。

注：准确来说，$\ge K$ 又分为 $\ge K$ 和 $\ge K+1$ ，同时，根据过程和定义，显然 $<K$ 里面有恰好 $K-1$ 个数字。

操作次数：$n\log_{2}{K}$ 左右，显然，这个做法完全优于上面的做法。

还没有明白怎么做的可以直接看代码，很好看懂的，我讲的确实有点抽象。

代码来自：https://uoj.ac/submission/243331 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cassert>
#include "kth.h"

using namespace std;
   
#define fi first
#define se second
#define rep(i,s,t) for(int i=(s),_t=(t);i<_t;++i)
#define per(i,s,t) for(int i=(t)-1,_s=(s);i>=_s;--i)
#define bug(x) cerr<<#x<<" = "<<(x)<<" "
#define debug(x) cerr<<#x<<" = "<<(x)<<"\n"

typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
   
template<class T>void rd(T &x){
	static int f;static char c;
	f=1;x=0;
	while(c=getchar(),c<48)if(c=='-')f=-1;
	do x=x*10+(c&15);
	while(c=getchar(),c>47);
	x*=f;
}
template<class T>void prin(T x){
	if(x<0)putchar('-'),x=-x;
	else if(!x){putchar('0');return ;}
	static int stk[100],tp;
	while(x)stk[tp++]=x%10,x/=10;
	while(tp)putchar(stk[--tp]^48);
}
template<class T>void ptk(T x){prin(x);putchar(' ');}
template<class T>void ptn(T x){prin(x);putchar('\n');}
template<class T>void Min(T &a,T b){if(b<a)a=b;}
template<class T>void Max(T &a,T b){if(a<b)a=b;}

const int N=(int)1e5+5;

int A[N],B[N],C[N];
//int get_a(int x);
//int get_b(int x);
//int get_c(int x);
//int get_a(int x){
//	return 1;
//	
//}
//int get_b(int x){
//	return 1;
//
//}
//int get_c(int x){
//	return 1;
//}
int Find_a(int x){
	if(x==0)return 0;
	if(A[x])return A[x];
	return A[x]=get_a(x-1);
}
int Find_b(int x){
	if(x==0)return 0;
	if(B[x])return B[x];
	return B[x]=get_b(x-1);
}
int Find_c(int x){
	if(x==0)return 0;
	if(C[x])return C[x];
	return C[x]=get_c(x-1);
}
int query_kth(int na, int nb, int nc, int K){
	int L[3]={0,0,0},R[3]={na,nb,nc},mid[3],could[3];
	int ans=(int)1e9;pii arr[3];
	while(L[0]<=R[0]||L[1]<=R[1]||L[2]<=R[2]){
		int sum=0;
		rep(i,0,3){
			if(L[i]<=R[i])mid[i]=(L[i]+R[i])>>1;
			else mid[i]=could[i];
			sum+=mid[i];
		}
		arr[0]=pii(Find_a(mid[0]),0);
		arr[1]=pii(Find_b(mid[1]),1);
		arr[2]=pii(Find_c(mid[2]),2);
		sort(arr,arr+3);
		if(sum>=K){//找最大的 
			Min(ans,arr[2].fi);
			per(i,0,3){
				if(L[arr[i].se]<=R[arr[i].se]){
					R[arr[i].se]=mid[arr[i].se]-1;
					break;
				}
			}
		}else {//找最小的 
			rep(i,0,3){
				if(L[arr[i].se]<=R[arr[i].se]){
					could[arr[i].se]=mid[arr[i].se];
					L[arr[i].se]=mid[arr[i].se]+1;
					break;
				}
			}
		}
	}
	return ans;
}