codeforces D. Cyclic MEX

本文主要是介绍codeforces D. Cyclic MEX，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

思路

• 手模发现把第一个 $x$ 移到最末尾时，进入队列吐出大于等于 $x$ 的，保留小于 $x$ 的。模拟此过程。
• 如果队列里存 $n$ 个数的话，那么时间复杂度达到 $n^2$ 不可取。所以队列存储 $(x,f_x)$ 大小及其频率/次数。

Think Twice, Code Once
根据代码体会模拟过程

#include <bits/stdc++.h>
#define il inline
#define get getchar
#define put putchar
#define is isdigit
#define int long long
#define dfor(i,a,b) for(int i=a;i<=b;++i)
#define dforr(i,a,b) for(int i=a;i>=b;--i)
#define dforn(i,a,b) for(int i=a;i<=b;++i,put(10))
#define mem(a,b) memset(a,b,sizeof a)
#define memc(a,b) memcpy(a,b,sizeof a)
#define pr 114514191981
#define gg(a) cout<<a,put(32)
#define INF 0x7fffffff
#define tt(x) cout<<x<<'\n'
#define endl '\n'
#define ls i<<1
#define rs i<<1|1
#define la(r) tr[r].ch[0]
#define ra(r) tr[r].ch[1]
#define lowbit(x) (x&-x)
#define ct cin.tie(nullptr),ios_base::sync_with_stdio(false)
using namespace std;
typedef unsigned int ull;
typedef pair<int, int> pii;
int read(void) {int x=0,f=1;char c=get();while(!is(c)) (f=c==45?-1:1),c=get();while(is(c)) x=(x<<1)+(x<<3)+(c^48),c=get();return x*f;
}
void write(int x) {if (x < 0) x = -x, put(45);if (x > 9) write(x / 10);put((x % 10) ^ 48);
}
#define writeln(a) write(a), put(10)
#define writesp(a) write(a), put(32)
#define writessp(a) put(32), write(a)
const int N = 1e6 + 10, M = 1e5 + 10, SN = 1e3 + 10, mod = 998244353;
signed main() {int T = read();while (T--) {int n = read();vector<int> a(n + 1);for (int i = 1; i <= n; ++i) a[i] = read();deque<pii> dq;vector<int> f(n + 1);int sum = 0, Min = 0;for (int i = 1; i <= n; ++i) {++f[a[i]];while (f[Min]) ++Min;dq.push_back({Min, 1});sum += Min;}int ans = sum;for (int i = 1; i < n; ++i) {pii t = {a[i], 0};sum -= dq.front().first;--dq.front().second;if (!dq.front().second) dq.pop_front();while (!dq.empty() && a[i] <= dq.back().first) {sum -= dq.back().first * dq.back().second;t.second += dq.back().second;dq.pop_back();}sum += t.first * t.second + n;dq.push_back(t), dq.push_back({n, 1});ans = max(ans, sum);}writeln(ans);}return 0;
}

这篇关于codeforces D. Cyclic MEX的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---