Public Bike Management

1018 Public Bike Management

There is a public bike service in Hangzhou City which provides great convenience to the tourists from all over the world. One may rent a bike at any station and return it to any other stations in the city.

The Public Bike Management Center (PBMC) keeps monitoring the real-time capacity of all the stations. A station is said to be in perfect condition if it is exactly half-full. If a station is full or empty, PBMC will collect or send bikes to adjust the condition of that station to perfect. And more, all the stations on the way will be adjusted as well.

刷PAT的过程中遇到了两类排队问题,这里总结一下

• 所有人在同一时刻到达,如1014 Waiting in Line
• 每个人到达的时刻不同,如1017 Queueing at Bank

解决这类问题一个比较好的思路是递推. 对同一时刻到达的问题,可以每个窗口设置front和rear两个变量,分别表示队首和队尾离队时间.front值最小的队列就是应该插入的队列.入队元素的离队时间可以由rear+=current.duration递推给出.队首元素离队后,原来第二个元素成为新的队首元素.更新front+=header.duration.

Waiting in Line

1014 Waiting in Line

Suppose a bank has N windows open for service. There is a yellow line in front of the windows which devides the waiting area into two parts. The rules for the customers to wait in line are:

• The space inside the yellow line in front of each window is enough to contain a line with M customers. Hence when all the N lines are full, all the customers after (and including) the (NM+1)st one will have to wait in a line behind the yellow line.
• Each customer will choose the shortest line to wait in when crossing the yellow line. If there are two or more lines with the same length, the customer will always choose the window with the smallest number.
• Customer​i​​ will take T​i​​ minutes to have his/her transaction processed.
• The first N customers are assumed to be served at 8:00am.

Now given the processing time of each customer, you are supposed to tell the exact time at which a customer has his/her business done.

同学发过来一道有意思的题

For a given chemical formula represented by a string, count the number of atoms of each element contained in the molecule and return an object (associative array in PHP, Dictionary<string, int> in C#, Map<String,Integer> in Java).

For example:

var water = 'H2O';
parseMolecule(water); // return {H: 2, O: 1}

var magnesiumHydroxide = 'Mg(OH)2';
parseMolecule(magnesiumHydroxide); // return {Mg: 1, O: 2, H: 2}

var fremySalt = 'K4[ON(SO3)2]2';
parseMolecule(fremySalt); // return {K: 4, O: 14, N: 2, S: 4}

As you can see, some formulas have brackets in them. The index outside the brackets tells you that you have to multiply count of each atom inside the bracket on this index. For example, in Fe(NO3)2 you have one iron atom, two nitrogen atoms and six oxygen atoms.

Emergency

1003 Emergency

As an emergency rescue team leader of a city, you are given a special map of your country. The map shows several scattered cities connected by some roads. Amount of rescue teams in each city and the length of each road between any pair of cities are marked on the map. When there is an emergency call to you from some other city, your job is to lead your men to the place as quickly as possible, and at the mean time, call up as many hands on the way as possible.

Counting Leaves

1004 Counting Leaves

A family hierarchy is usually presented by a pedigree tree. Your job is to count those family members who have no child.

Input Specification:

Each input file contains one test case. Each case starts with a line containing 0<N<100, the number of nodes in a tree, and M (<N), the number of non-leaf nodes. Then M lines follow, each in the format:

什么是异常

「现代操作系统」和国内的教材都没有讲清楚「中断、异常」这一组概念，再加上自己懒，一直没弄出个所以然，今天看了CSAPP上的解释，醍醐灌顶。

对于特定的进程来说，程序计数器按照时间升序所得的序列反映了指令的执行顺序，即控制流。理论上说，程序的控制流在编译期就已经决定。而实际中，经常会出现一些需要暂停执行当前程序，而转去处理更高优先级任务的情况。在这个过程中，程序的控制流就发生了改变。CSAPP中把控制流的非自愿改变定义为异常。强调非自愿，是因为程序自己也可以改变控制流，但那不属于异常。

递归高亮

先来修正选择高亮的问题吧。我更愿意图片中的效果称为递归高亮。递归高亮可以看作是子节点都处于非递归高亮状态。这么想的话实现起来应该非常容易。但我希望FluentTreeView能够更灵活一些。最好通过属性来切换高亮模式。

这篇起我们正式开始实现FluentTreeView。先看看图片

TreeView左侧有一选择高亮，Item有一鼠标高亮。这两个高亮与整个TreeView一样宽。 再回想一下我们上一篇用Expander实现的TreeView，Item的缩进是如何实现的？

上一篇中我们用数据驱动界面的方式使用了TreeView。这一篇我们稍稍改一改TreeView的样式。把TreeView表示节点可以展开的小三角替换成Expander是个不错的开始。既能复习TreeView的可视化树，又避免步子太大扯到蛋。