Time Limit: 1 second
Memory Limit: 32 MB
【问题描述】
小明是一个非常喜欢读书的孩子，他有一个特别的书架，书架上摆放着他买的新书。当他决定要阅读某本图书时，他就把书从书架中取出，这时书架上就出现了空位，他会立即整理这些图书使图书之间不出现空位。小明总是将新书从左边塞入，由于书架的宽度是有限的，新加入的书可能把书架上另一端的图书挤出来。
小明的记忆力不好，他需要你的帮助，给你一系列的操作，请你计算出书架上摆放有几本图书，并把它们的编号按照从左到右的顺序输出。一共有三种操作：
添加操作A id w：从书架的左边塞入一本编号为id的图书，该图书的宽度为w，并向右推以确保该图书摆放在书架上。如果书架上图书的总宽度超过书架的宽度，那么不完全在书架内的图书将会从书架上掉下来。任何一本书的宽度都不会超过书架的宽度。如果编号为id的图书已经在书架上，则该操作无效。
删除操作R id：从书架上拿走一本编号为id的图书。如果编号为id的图书不在书架上，则该操作无效。
结束操作E：操作结束。
【输入格式】
输入数据的第一行是一个整数N(1≤N≤100,000)，表示书架的宽度。紧接着是一系列的操作，添加操作的格式如下：
A id w 其中id是图书的编号，w是图书的宽度，id和w均为整数(0<id≤100,000,0<w≤N)。
删除操作的格式如下：
R id
其中id为图书的编号，id为整数(0<id≤100,000)。
字符‘E’表示操作结束。
需要注意的是，从书架上拿下编号为id的图书后再放一本编号为id的图书，它们的宽度可能不同。操作数不会超过200,000。
【输出格式】
输出一个整数S表示书架上图书的数量，接下来一行按照从左到右的顺序输出书架上图书的编号(编号之间有一个空格，最后一个编号后不需要空格)。
【输入样例1】
5
A 1 1
A 2 1
A 3 1
R 2
A 2 2
A 5 1
R 5
R 4
A 6 1
A 7 4
E
【输出样例1】
2
7 6
【输入样例2】
5
E
【输出样例2】
0
【输入样例3】
3
A 1 2
A 2 1
R 3
A 2 3
E
【输出样例3】
2
2 1
【题目链接】:http://noi.qz5z.com/viewtask.asp?id=t012
【题意】
【题解】
/*
用链表来模拟这个过程;
一个计数器sum记录总的长度;
先把新的书加进去;
然后看看总长度有没有大于N;
大于N了
就在链表的尾端将最末端的书给去除掉;
一开始可以先加两个哨兵节点(最左和最右,方便插入和查找最末的位置);
删除的时候就是链表节点的删除;然后减掉那本数的宽度;
修改那本书是否在链表中;
看看sum是否还大于N,还大于N的话就重复上述操作。
*/
【完整代码】
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define rei(x) scanf("%d",&x)
#define rel(x) scanf("%lld",&x)
#define ref(x) scanf("%lf",&x)
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
const int dx[9] = { 0,1,-1,0,0,-1,-1,1,1 };
const int dy[9] = { 0,0,0,-1,1,-1,1,-1,1 };
const double pi = acos(-1.0);
const int N = 1e5+100;
struct point
{
int w,id;
point *next,*pre;
};
struct abc
{
int in;
point *wh;
};
int n,num=0;
int now;//总长度可能爆int
char s[5];
point *h, *t,*p;
abc a[N];
void in()
{
rei(n);
h = new point, t = new point;
h->next = t;
t->pre = h;
}
void cl()
{
scanf("%s", s);
while (s[0] != 'E')
{
int id, w;
if (s[0] == 'A')
{
rei(id), rei(w);
if (!a[id].in)
{
a[id].in = 1;
num++;
now += w;
p = new point;
p->w = w, p->id = id;
h->next->pre = p;
p->next = h->next;
h->next = p;
p->pre = h;
a[id].wh = p;
while (now > n)
{
p = t->pre;
a[p->id].in = 0;
now -= p->w;
p->pre->next = t;
t->pre = p->pre;
num--;
}
}
}
else
{
rei(id);
if (a[id].in)
{
a[id].in = 0;
num--;
p = a[id].wh;
p->pre->next = p->next;
p->next->pre = p->pre;
now -= p->w;
}
}
scanf("%s", s);
}
}
void o()
{
printf("%d
", num);
p = h->next;
int cnt = 0;
while (p != t)
{
printf("%d", p->id);
cnt++;
if (cnt == num)
puts("");
else
putchar(' ');
p = p->next;
}
}
int main()
{
//freopen("F:\rush.txt", "r", stdin);
in();
cl();
o();
//printf("
%.2lf sec
", (double)clock() / CLOCKS_PER_SEC);
return 0;
}