Hotel

* Line 1: Two space-separated integers: N and M
* Lines 2..M+1: Line i+1 contains request expressed as one of two possible formats: (a) Two space separated integers representing a check-in request: 1 and Di (b) Three space-separated integers representing a check-out: 2, Xi, and Di

* Lines 1.....: For each check-in request, output a single line with a single integer r, the first room in the contiguous sequence of rooms to be occupied. If the request cannot be satisfied, output 0.

C++14(g++5.4) 解法, 执行用时: 590ms, 内存消耗: 876K, 提交时间: 2019-07-27 15:44:53

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int room,t,num[100000];
int main()
{
	
	scanf("%d%d",&room,&t);
	for(int i = room;i > 0;i--)
	{
		num[i] = num[i+1]+1;
	}
	for(int i = 0;i < t;i++)
	{
		int temp;
		scanf("%d",&temp);
		if(temp == 1)
		{
			int nu,flag=1;
			scanf("%d",&nu);
			for(int i = 1;i <= room;i++)
			{
				if(num[i] >= nu)
				{
					flag = 0;
					printf("%d\n",i);
					for(int k = i;k < i + nu;k++)
					{
						num[k] = 0;
					}
					break;
				}
			}
			if(flag)puts("0");
			
		}
		else
		{
			int l,r;
			scanf("%d%d",&l,&r);
			for(int i = l + r - 1;i >= 1;i--)
			{
				if(i < l && num[i] == 0)break;
				num[i] = num[i + 1] + 1;
			}
			
		}
	}
}

C++11(clang++ 3.9) 解法, 执行用时: 730ms, 内存消耗: 868K, 提交时间: 2019-07-22 18:53:55

#include<stdio.h>
#define maxn 50005
int a[maxn];
int main()
{
	int n,m;
	scanf("%d %d",&n,&m);
	for(int i=n;i>=1;i--)
	{
		a[i]=a[i+1]+1;
	}
	while(m--)
	{
		int p;
		scanf("%d",&p);
		if(p==1)
		{
			int num,flag=1;
			scanf("%d",&num);
			for(int i=1;i<=n;i++)
			{
				if(a[i]>=num)
				{
					flag=0;
					printf("%d\n",i);
					for(int k=i;k<i+num;k++)
					{
						a[k]=0;
					}
					break;
				}
			}
			if(flag) printf("0\n");
		}
		if(p==2)
		{
			int l,r;
			scanf("%d %d",&l,&r);
			for(int i=l+r-1;i>=1;i--)
			{
				if(i<l&&a[i]==0) break;
				a[i]=a[i+1]+1;
			}
		}
	}
	return 0;
 }

详情