首页 > 代码库 > Codeforces 46D Parking Lot(贪心模拟)

Codeforces 46D Parking Lot(贪心模拟)

Codeforces 46D Parking Lot

题目链接

开线段树专题开出了这题。。看似要用区间合并求连续最大区间,其实不需要。因为询问才100个,直接set暴力去模拟即可,每次车进来就从左往右找到一个合适位置

代码:

#include <cstdio>
#include <cstring>
#include <set>
using namespace std;

const int N = 100005;
int L, b, f, n;
set<int> g;
set<int>::iterator u, v;
int save[N][2];

int main() {
	scanf("%d%d%d", &L, &b, &f);
	scanf("%d", &n);
	g.insert(-b); g.insert(L + f);
	int op, x;
	for (int i = 1; i <= n; i++) {
		scanf("%d%d", &op, &x);
		if (op == 1) {
			int flag = 1;
			for (u = g.begin(); u != g.end(); u++) {
				v = u; v++;
				if (v != g.end() && *u + b + x + f <= *v) {
					g.insert(*u + b); g.insert(*u + b + x);
					save[i][0] = *u + b; save[i][1] = *u + b + x;
					printf("%d\n", *u + b);
					flag = 0;
					break;
				}
				u++;
			}
			if (flag) printf("-1\n");
		} else {
			g.erase(save[x][0]);
			g.erase(save[x][1]);
		}
	}
	return 0;
}


Codeforces 46D Parking Lot(贪心模拟)