脚本宝典收集整理的这篇文章主要介绍了2022.3.22 代码源每日一题div1 #608. 字典序最小,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
道理是这么个道理,但实现一下细节太多,把上述思路转换一下,循环(1-m),每次维护优先队列把大于等于(a[i])的都弹掉,加入当前数字,如果当前数字(cnt)减为零了,就把队列里所有小于等于当前值的数以及当前值都加入答案,为什么呢?因为题目里满足(a[i])中必然会出现按(1-n)的每一个数,也就是说我们必须要选择(1-n)中的每一个数,那当前值的(cnt)都要变为零了我们还不选,以后就没得选了,所以把队列里比当前值小的都加进入,再把当前值加入
#include<algorithm>
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
#define x first
#define y second
#define ll long long
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define rep(i, a, b) for(int i = a; i <= b; ++i)
#define per(i, a, b) for(int i = a; i >= b; --i)
#define clr(a, b) memset((a),b,sizeof(a))
using namespace std;
inline int read(){
int s = 0, w = 1; char ch = getchar();
while(ch < '0' || ch > '9') { if(ch == '-') w = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9') { s = (s << 3) + (s << 1) + (ch ^ 48); ch = getchar(); }
return s * w;
}
const int N = 1e6 + 50;
int n, m, num, ans[N], a[N], cnt[N], vis[N];
deque <int> q;
int main() {
m = read(); n = read();
rep(i, 1, m) {
a[i] = read();
cnt[a[i]] ++;
}
rep(i, 1, m) {
if(cnt[a[i]] == 0) continue;
cnt[a[i]] --;
while(vis[a[i]] == 0 && q.size() && q.back() >= a[i]) {
vis[q.back()] = 0;
q.pop_back();
}
if(vis[a[i]] == 0) {
q.push_back(a[i]);
vis[a[i]] = 1;
}
if(cnt[a[i]] == 0) {
while(q.size() && q.front() <= a[i]) {
int x = q.front();
q.pop_front();
ans[++ num] = x;
cnt[x] = 0;
}
}
}
rep(i, 1, num) {
if(i != 1) printf(" ");
printf("%d", ans[i]);
}
return 0;
}
另一种单调栈的写法
注意每次弹出元素需要保证后面还有这个元素,若后面没有这个元素我们又把他弹出了,以后就再也没得选了,而这个题要求我们(1-n)的每个数都要出现一次,就不满足题目要求了#include<algorithm>
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#define x first
#define y second
#define ll long long
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define rep(i, a, b) for(int i = a; i <= b; ++i)
#define per(i, a, b) for(int i = a; i >= b; --i)
#define clr(a, b) memset((a),b,sizeof(a))
using namespace std;
inline int read(){
int s = 0, w = 1; char ch = getchar();
while(ch < '0' || ch > '9') { if(ch == '-') w = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9') { s = (s << 3) + (s << 1) + (ch ^ 48); ch = getchar(); }
return s * w;
}
const int N = 1e6 + 50;
int n, k, a[N], vis[N], lst[N];
int main() {
n = read(); k = read();
rep(i, 1, n) {
a[i] = read();
lst[a[i]] = i;
}
stack <int> stk;
rep(i, 1, n) {
if(vis[a[i]]) continue;
while(stk.size() && stk.top() > a[i] && lst[stk.top()] > i) {
vis[stk.top()] = 0;
stk.pop();
}
stk.push(a[i]);
vis[a[i]] = 1;
}
vector <int> ans;
while(stk.size())
ans.push_back(stk.top()), stk.pop();
reverse(ans.begin(), ans.end());
rep(i, 0, ans.size() - 1) {
if(i) printf(" ");
printf("%d", ans[i]);
}
return 0;
}
以上是脚本宝典为你收集整理的2022.3.22 代码源每日一题div1 #608. 字典序最小全部内容,希望文章能够帮你解决2022.3.22 代码源每日一题div1 #608. 字典序最小所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。