深圳企业网站建设服务,快速网站推广优化,高端网站建设加盟,安阳区号后三位传送门
题意#xff1a; 给nnn个数#xff0c;一个kkk#xff0c;求aaa中包含1−k1-k1−k且字典序最小的子序列。
思路1#xff1a; 记p[i]p[i]p[i]为iii出现的最后位置#xff0c;让后维护一个栈#xff0c;当这个数不在栈里时将其入栈#xff0c;入栈的时候跟栈顶比…传送门
题意 给nnn个数一个kkk求aaa中包含1−k1-k1−k且字典序最小的子序列。
思路1 记p[i]p[i]p[i]为iii出现的最后位置让后维护一个栈当这个数不在栈里时将其入栈入栈的时候跟栈顶比较当a[i]stk[top]且p[stk[top]]ia[i]stk[top] 且p[stk[top]]ia[i]stk[top]且p[stk[top]]i的时候弹出栈顶即当这个数比栈顶小且后面还有栈顶元素可以替换他的时候出栈。这样最后栈中元素即为答案。 复杂度O(n)O(n)O(n)
思路2 用线段树维护区间中a[i]a[i]a[i]值最小的位置让后记录一下每个数最后出现的位置一次找kkk个数。每次查询的区间就是[pre,s.begin()][pre,s.begin()][pre,s.begin()]让后返回的位置即为当前选的数的位置其中sss是setsetset存每个数最后出现的位置preprepre是上次取的数的位置1。来讨论一下这样为什么是正确的。首先我们要字典序最小贪心的想肯定是前面越小越好假设序列为[4,4,2,1,3,4,1],k3[4,4,2,1,3,4,1],k3[4,4,2,1,3,4,1],k3初始的时候pre1pre1pre1s.begin()3s.begin()3s.begin()3让后我们找[1,3][1,3][1,3]最小值的下标为什么要在[1,3][1,3][1,3]中找呢因为333位置是222最后一次出现的位置如果你跑[1,4][1,4][1,4]中找的话你会选到111这样你第一个数就是111了而且pre5pre5pre5代表你之后都不会选到222这个数了所以要以最后出现的位置为界来找前面出现的最小值。让后每次都找当前区间最小值最左边的位置让后输出即可。
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].ltr[u].r1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N1000010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n,k;
int a[N];
int stk[N],top;
int p[N],cnt[N];int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);scanf(%d%d,n,k);for(int i1;in;i) scanf(%d,a[i]),p[a[i]]i;for(int i1;in;i){if(cnt[a[i]]) continue;while(topstk[top]a[i]p[stk[top]]i) top--,cnt[stk[top1]]0;stk[top]a[i]; cnt[a[i]]1;}for(int i1;itop;i) printf(%d ,stk[i]); puts();return 0;
}
/**/
