Codeforces Round #615 (Div. 3)D. MEX maximizing(思维)

题目地址：https://codeforces.com/contest/1294/problem/D

题意：你有一个空白数组，需要向里面插入n个数字，这些数字可以加k或减k任意次。问每次加入后数组内的没有出现的最小的非负整数是多少
例如：n = 7, k = 301220010第一次插入0，此时没有出现的最小的非负整数是1；数组{0}第二次插入1，此时没有出现的最小的非负整数是2；数组{0，1}第三次插入2，此时没有出现的最小的非负整数是3；数组{0，1，2}第四次插入2，因为k=3，并且数组内已经有一个2了，所以我们将2+3=5；此时没有出现的最小的非负整数是3；数组{0，1，2，5}第五次插入0，因为k=3，并且数组内已经有一个0了，所以我们将0+3=3；此时没有出现的最小的非负整数是4；数组{0，1，2，3，5}第六次插入0，因为k=3，并且数组内已经有一个0和3了，所以我们将0+3+3=6；此时没有出现的最小的非负整数是4；数组{0，1，2，3，5，6}第七次插入10，因为k=3，所以我们将10-3-3=4，此时没有出现的最小非负整数是7；数组{0，1，2，3，4，5，6}思路：由于每个数字可以增加或减少任意次数的k，所以在存储的时候存储%kn的范围是4e5，所以数组a开到400005。ans作为每次插入后输出的结果，不断递增，每次查询a[ans%k]是不是等于1，如果等于1代表之前的步骤中插入过一个是ans%k的倍数的数字，将ans++，查询下一个数

没看懂可以照着代码自己用手跑一遍上面的样例

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define dd double
#define PI acos(-1.0)
#define f(i, x, y) for(ll i = x; i < y; i++)
using namespace std;
const ll MAXN = 2e5 + 5;ll a[400005];int main() {ios::sync_with_stdio(false);cin.tie(0);ll n, k; cin >> n >> k;f(i, 0, n) {a[i] = 0;}ll ans = 0;f(i, 0, n) {ll x; cin >> x;a[x % k]++;while (a[ans % k] != 0) {a[ans % k]--;ans++;}cout << ans << endl;}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！