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;
}