丑数 Humble Numbers

https://www.luogu.org/problemnew/show/P2723

题解：

C++版本一

题解：STL+优化

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
struct node{
    int v;
    int i;
    bool operator < (const node &S)const{
        return v>S.v;
    }
};
ll a[N];
priority_queue<node>heap;
char str;
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    scanf("%d%d",&k,&n);
    for(ll i=1;i<=k;i++){
        scanf("%lld",&a[i]);
    }
    heap.push({1,1});
    node humble;
    t=n;
    n++;
    while(n--){
        humble=heap.top();
        heap.pop();
        for(int i=humble.i;i<=k;i++){
            ll num=humble.v*a[i];
            if(num<=(1ll<<31)-1)
                heap.push({num,i});
        }
    }
    printf("%d\n",humble.v);
    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

C++版本二

题解：贪心

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int i,j,n,m,k;
long long a[150],s[100011],f[100011];

int main(){
    cin>>k>>n;
    for(i=1;i<=k;i++) cin>>a[i];
    f[0]=1;
    for(i=1;i<=n;i++){
        m=2147483647;
        for(int j=1;j<=k;j++){
            while(a[j]*f[s[j]]<=f[i-1]) s[j]++;
            if(a[j]*f[s[j]]<m) m=a[j]*f[s[j]];
        }
        f[i]=m;
    }
    cout<<f[n]<<endl;
    return 0;
}

C++版本三

题解：平衡树

#include <iostream>
#include <cstdio>

using namespace std;

const int S = 1 << 20;
char frd[S], *hed = frd + S;
const char *tal = hed;

inline char nxtChar()
{
    if (hed == tal)
     fread(frd, 1, S, stdin), hed = frd;
    return *hed++;
}

inline int get()
{
    char ch; int res = 0;
    while (!isdigit(ch = nxtChar()));
    res = ch ^ 48;
    while (isdigit(ch = nxtChar()))
     res = res * 10 + ch - 48;
    return res;
}

typedef long long ll;
const int N = 11e4 + 5;
ll Int = 2147483647ll;
int fa[N], lc[N], rc[N], sze[N], val[N];
int T, n, k, rt, top, stk[N], a[N];

inline void Push(int x) {sze[x] = sze[lc[x]] + sze[rc[x]] + 1;}

inline void Rotate(int x)
{
    int y = fa[x], z = fa[y];
    int b = (lc[y] == x ? rc[x] : lc[x]);
    fa[y] = x; fa[x] = z;
    if (b) fa[b] = y;
    if (z) (lc[z] == y ? lc[z] : rc[z]) = x;
    if (lc[y] == x) rc[x] = y, lc[y] = b;
     else lc[x] = y, rc[y] = b;
    Push(y);
}

inline bool Which(int x) {return lc[fa[x]] == x;}

inline void Splay(int x, int tar)
{
    while (fa[x] != tar)
    {
        if (fa[fa[x]] != tar)
         Which(fa[x]) == Which(x) ? Rotate(fa[x]) : Rotate(x);
        Rotate(x); 
    }
    Push(x);
    if (!tar) rt = x;
}

inline void Insert(int vi)
{
    int x = rt, y = 0, dir;
    while (x)
    {
        y = x;
        if (val[x] == vi) return ;
        if (val[x] > vi) x = lc[x], dir = 0;
         else x = rc[x], dir = 1;  
    }
    int w = y; if (y) ++sze[y];
    while (fa[w]) ++sze[w = fa[w]];
    x = top ? stk[top--] : ++T;
    fa[x] = y; val[x] = vi; sze[x] = 1;
    if (y) (dir ? rc[y] : lc[y]) = x; 
    Splay(x, 0);
}

inline void Join(int x, int y)
{
    int w = y;
    while (lc[w]) w = lc[w];
    lc[fa[x] = w] = x; fa[rt = y] = 0;
    Splay(w, 0);
}

inline void Delete(int x)
{
    Splay(x, 0);stk[++top] = x;
    int L = lc[x], R = rc[x];
    lc[x] = rc[x] = 0;
    if (!L || !R) fa[rt = L + R] = 0;
     else Join(L, R);
}

inline int GetKth(int k)
{
    int x = rt;
    while (x)
    {
        if (k <= sze[lc[x]])
         x = lc[x];
        else 
        {
            k -= sze[lc[x]] + 1;
            if (!k) return x;
            x = rc[x];
        }
    }
    return 0;
}

inline void Print(int x)
{
    if (!x) return ;
    Print(lc[x]); Print(rc[x]); 
    stk[++top] = x; 
    fa[x] = lc[x] = rc[x] = 0;
}

inline int FindMin() {int x = rt; while (lc[x]) x = lc[x]; return x;}

int main()
{
    k = get(); n = get(); int x, cnt = 0; ll y;
    for (int i = 1; i <= k; ++i) Insert(a[i] = get());
    while (++cnt <= n)
    {
        y = val[x = FindMin()]; Delete(x);
        for (int i = 1; i <= k; ++i) 
         if (y * a[i] < Int) Insert(y * a[i]);
          else break;
        if (sze[rt] + cnt >= n) 
        {
            Int = val[x = GetKth(n - cnt)]; Splay(x, 0); 
            Print(rc[x]); rc[x] = 0; Push(x);
        }
    }
    cout << y << endl;
}