首页 > ACM题库 > HDU-杭电 > hdu 2726 Overflowing Bookshelf[解题报告]C++
2014
02-14

hdu 2726 Overflowing Bookshelf[解题报告]C++

Overflowing Bookshelf

问题描述 :

Agnes C. Mulligan is a fanatical bibliophile � she is constantly buying new books, and trying to find space for those books. In particular, she has a shelf for her “to be read” books, where she puts her newest books. When she decides to read one of these books, she removes it from the shelf, making space for more books. Sometimes, however, she buys a new book and puts it on the shelf, but because of limited space, this pushes one or more books off the shelf at the other end. She always adds books on the left side of the shelf, making books fall off the right side. Of course, she can remove a book from any location on the shelf when she wants to read one.

Your task will be to write a simulator that will keep track of books added and removed from a shelf. At the end of the simulation, display the books remaining on the shelf, in order from left to right. Books in each simulation will be identified by a unique, positive integer, 0 < I ≤ 100. There are three types of events in the simulation:
Add: A new book is pushed on the left end of the shelf, pushing other books to the right as needed. No book moves to the right unless it is pushed by an adjacent (touching) book on its left. Any book that is not entirely on the shelf falls off the right edge. No single book will ever be wider than the given shelf. No book that is currently on the shelf will be added again.
Remove: If the book is on the shelf, then the book is removed from the shelf, leaving a hole. If the book isn’t on the shelf, the operation is ignored.
End: End the simulation for this case and print the contents of the shelf.

输入:

The input file will contain data for one or more simulations. The end of the input is signalled by a line containing -1. Each simulation will begin with the integer width of the shelf, s, 5 ≤ s ≤ 100, followed by a series of add and remove events. An add event is a single line beginning with an upper case ‘A’ followed by the book ID, followed by the integer width of the book, w, 0 < w ≤ s. A remove event is a single line beginning with an upper case ‘R’ followed by the the book ID. Finally, the end event is a line containing only a single upper case ‘E’. Each number in an event is preceded by a single blank.

输出:

The input file will contain data for one or more simulations. The end of the input is signalled by a line containing -1. Each simulation will begin with the integer width of the shelf, s, 5 ≤ s ≤ 100, followed by a series of add and remove events. An add event is a single line beginning with an upper case ‘A’ followed by the book ID, followed by the integer width of the book, w, 0 < w ≤ s. A remove event is a single line beginning with an upper case ‘R’ followed by the the book ID. Finally, the end event is a line containing only a single upper case ‘E’. Each number in an event is preceded by a single blank.

样例输入:

10
R 3
A 6 5
A 42 3
A 3 5
A 16 2
A 15 1
R 16
E
7
A 49 6
A 48 2
R 48
E
5
A 1 1
A 2 1
A 3 1
R 2
A 4 1
A 5 1
R 5
R 4
A 6 1
A 7 4
E
-1

样例输出:

PROBLEM 1: 15 3
PROBLEM 2:
PROBLEM 3: 7 6

http://acm.pku.edu.cn/JudgeOnline/problem?id=2705

貌似是1886 Borrows的简化版,再次练练链表。

Source Code

Problem: 2705 User: dizem Memory: 208K Time: 0MS Language: C++ Result: Accepted

  • Source Code #include <stdio.h>struct book{ int width, id; book *next;}; int s_width, cur_width, last_id; void newhead(book *&head, int width, int id){ book *p = new book; p->width = width; p->id = id; p->next = head; head = p; cur_width += width;//增加现有宽度}void Delete(book *&head, int id){ book *p, *q; if(!cur_width) return;//空书架 if(head->id == id){//待删除的id在链首 p = head; head = head->next; cur_width -= p->width; delete p; } else{ if(head->next == NULL) return;//待删除的id不存在 p = head; while(p->next){ if((p->next)->id == id) break; p = p->next; } if(p->next->next == NULL) last_id = p->id; q = p->next; p->next = q->next; cur_width -= q->width; delete q; }}void Free_list(book *&head){ book *p; while(head){ p = head; head = head->next; delete p; } cur_width = 0;}int main(){ char act; int id, width, t = 0; cur_width = 0; book *head, *p; while(scanf("%d", &s_width) && s_width+1) { head = NULL; while(scanf("%c", &act) && act!=’E') { if(act == ‘A’)//增加数目 { scanf("%d%d", &id, &width); if(!cur_width) last_id = id;//记录最后一本书的ID newhead(head, width, id); while(cur_width > s_width) Delete(head, last_id); //反复挤出最后一本书,直到书的总宽度小于书架 } else if(act == ‘R’)//移除数目 { scanf("%d", &id); Delete(head, id); } } printf("PROBLEM %d:", ++t); p = head; while(p)//打印剩余的书目 { printf(" %d", p->id); p = p->next; } printf("\n"); Free_list(head);//删除链表 } return 0;}

解题转自:http://hi.baidu.com/dizemmm/item/d907a0d11a85ff332b35c7eb


  1. 问题3是不是应该为1/4 .因为截取的三段,无论是否能组成三角形, x, y-x ,1-y,都应大于0,所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.