3699405_tle.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <set>
#include <stdio.h>
#include <algorithm>

using namespace std;

struct node
{
	int k, n;
	node (int kk, int nn)
	{
		k = kk;
		n = nn;
	}

	bool operator < (const node &t)	const
	{
		return n < t.n;
	}
};

set <node> s;
set <node>::iterator it;

int main()
{
	int t, k, n;
	char str[2];
	int r, g;
	int max = 0, cas = 1;

	while (scanf("%d", &t) == 1 && t != 0)
	{
		printf("Case %d:\n", cas++);
		k = 1;
		s.clear();
		while (t-- != 0)
		{
			scanf("%s%d", str, &n);
			if (str[0] == 'B')
			{
				s.insert(node(k++, n));
				if (n > max)
					max = n;
			}
			else
			{
				if (s.empty())
				{
					puts("-1");
					continue;
				}
				r = 500000;g = 0;
				node tmp = node(0, 0);
				it = s.begin();
				while ((it = upper_bound(it, s.end(), tmp)) != s.end())
				{
					node nd = *it;
					int tn = nd.n % n;
					int tk = nd.k;
					if (tn < r || (tn == r && tk > g))
					{
						r = tn;
						g = tk;
					}
					tmp.n = (nd.n / n + 1 ) * n;
				}
				printf("%d\n", g);
			}
		}
		puts("");
	}
	return 0;
}