分类： Code

Suppose a bank has K windows open for service. There is a yellow line in front of the windows which devides the waiting area into two parts. All the customers have to wait in line behind the yellow line, until it is his/her turn to be served and there is a window available. It is assumed that no window can be occupied by a single customer for more than 1 hour.

Now given the arriving time T and the processing time P of each customer, you are supposed to tell the average waiting time of all the customers.

Input Specification:

Each input file contains one test case. For each case, the first line contains 2 numbers: N (<=10000) – the total number of customers, and K (<=100) – the number of windows. Then N lines follow, each contains 2 times: HH:MM:SS – the arriving time, and P – the processing time in minutes of a customer. Here HH is in the range [00, 23], MM and SS are both in [00, 59]. It is assumed that no two customers arrives at the same time.

Notice that the bank opens from 08:00 to 17:00. Anyone arrives early will have to wait in line till 08:00, and anyone comes too late (at or after 17:00:01) will not be served nor counted into the average.

Output Specification:

For each test case, print in one line the average waiting time of all the customers, in minutes and accurate up to 1 decimal place.

Sample Input:
7 3
07:55:00 16
17:00:01 2
07:59:59 15
08:01:00 60
08:00:00 30
08:00:02 2
08:03:00 10
Sample Output:
8.2

题目大意：有n个客户，k个窗口。已知每个客户的到达时间和需要的时长，如果有窗口就依次过去，如果没有窗口就在黄线外等候（黄线外只有一个队伍，先来先服务），求客户的平均等待时长。银行开放时间为8点到17点，再8点之前不开门，8点之前来的人都要等待，在17点后来的人不被服务。

分析：用一个结构体存储客户的到达时间和办理业务时间~首先把所有hh:mm:ss格式的时间全化成以当天0点为基准的秒数。注意晚于17:00的客户不算在内～既然客户是排队的，那么排序后对于每个客户都是同样的处理方式～使用一个优先队列维护窗口办理完业务的时间～如果最早结束服务的窗口时间早于客户的到达时间，不需要等待，直接执行 q.push(p[i].come + p[i].time);否则客户的等待时间是q.top() – p[i].come～

PS：感谢@琦子块提供的更优解～

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 example, suppose that a bank has 2 windows and each window may have 2 custmers waiting inside the yellow line. There are 5 customers waiting with transactions taking 1, 2, 6, 4 and 3 minutes, respectively. At 08:00 in the morning, customer1 is served at window1 while customer2 is served at window2. Customer3 will wait in front of window1 and customer4 will wait in front of window2. Customer5 will wait behind the yellow line.

At 08:01, customer1 is done and customer5 enters the line in front of window1 since that line seems shorter now. Customer2 will leave at 08:02, customer4 at 08:06, customer3 at 08:07, and finally customer5 at 08:10.

Input

Each input file contains one test case. Each case starts with a line containing 4 positive integers: N (<=20, number of windows), M (<=10, the maximum capacity of each line inside the yellow line), K (<=1000, number of customers), and Q (<=1000, number of customer queries).

The next line contains K positive integers, which are the processing time of the K customers.

The last line contains Q positive integers, which represent the customers who are asking about the time they can have their transactions done. The customers are numbered from 1 to K.

Output

For each of the Q customers, print in one line the time at which his/her transaction is finished, in the format HH:MM where HH is in [08, 17] and MM is in [00, 59]. Note that since the bank is closed everyday after 17:00, for those customers who cannot be served before 17:00, you must output “Sorry” instead.

Sample Input
2 2 7 5
1 2 6 4 3 534 2
3 4 5 6 7
Sample Output
08:07
08:06
08:10
17:00
Sorry

题目大意：n个窗口，每个窗口可以排队m人。有k位用户需要服务，给出了每位用户需要的minute数，所有客户在8点开始服务，如果有窗口还没排满就入队，否则就在黄线外等候。如果有某一列有一个用户走了服务完毕了，黄线外的人就进来一个。如果同时就选窗口数小的。求q个人的服务结束时间。
如果一个客户在17:00以及以后还没有开始服务（此处不是结束服务是开始17:00）就不再服务输出sorry；如果这个服务已经开始了，无论时间多长都要等他服务完毕。
分析：设立结构体，里面包含poptime为队首的人出队（结束）的时间，和endtime为队尾的人结束的时间。poptime是为了让黄线外的人可以计算出哪一个队列先空出人来（poptime最小的那个先有人服务完毕），endtime是为了入队后加上自己本身的服务所需时间可以计算出自己多久才能被服务完毕～且前一个人的endtime可以得知自己是不是需要被Sorry（如果前一个人服务结束时间超过17:00，自己当前入队的人就是sorry），还有一个queue表示所有当前该窗口的排队队列。
对于前m*n个人，也就是排的下的情况下，所有人依次到窗口前面排队。对于m*n之后的人，当前人选择poptime最短的入队，让队伍的第一个人出列），如果前面一个人导致的endtime超过17点就标记自己的sorry为true。
计算时间的时候按照分钟计算，最后再考虑08点开始和转换为小时分钟的形式会比较简便。

Shopping in Mars is quite a different experience. The Mars people pay by chained diamonds. Each diamond has a value (in Mars dollars M$). When making the payment, the chain can be cut at any position for only once and some of the diamonds are taken off the chain one by one. Once a diamond is off the chain, it cannot be taken back. For example, if we have a chain of 8 diamonds with values M$3, 2, 1, 5, 4, 6, 8, 7, and we must pay M$15. We may have 3 options:

1. Cut the chain between 4 and 6, and take off the diamonds from the position 1 to 5 (with values 3+2+1+5+4=15).
2. Cut before 5 or after 6, and take off the diamonds from the position 4 to 6 (with values 5+4+6=15).
3. Cut before 8, and take off the diamonds from the position 7 to 8 (with values 8+7=15).
Now given the chain of diamond values and the amount that a customer has to pay, you are supposed to list all the paying options for the customer.

If it is impossible to pay the exact amount, you must suggest solutions with minimum lost.

Input Specification:

Each input file contains one test case. For each case, the first line contains 2 numbers: N (<=105), the total number of diamonds on the chain, and M (<=108), the amount that the customer has to pay. Then the next line contains N positive numbers D1 … DN (Di<=103 for all i=1, …, N) which are the values of the diamonds. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print “i-j” in a line for each pair of i <= j such that Di + … + Dj = M. Note that if there are more than one solution, all the solutions must be printed in increasing order of i.

If there is no solution, output “i-j” for pairs of i <= j such that Di + … + Dj > M with (Di + … + Dj – M) minimized. Again all the solutions must be printed in increasing order of i.

It is guaranteed that the total value of diamonds is sufficient to pay the given amount.

Sample Input 1:
16 15
3 2 1 5 4 6 8 7 16 10 15 11 9 12 14 13
Sample Output 1:
1-5
4-6
7-8
11-11
Sample Input 2:
5 13
2 4 5 7 9
Sample Output 2:
2-4
4-5
题目大意，求一串的数字中连续的一段，使得这个连续的段内数字的和恰好等于所期望的值m。如果不能找到恰好等于，就找让自己付出最少的价格（总和必须大于等于所给值）的那段区间。求所有可能的结果。
分析：一开始用的简单模拟，有两个超时了。后来想到因为sum数组是递增的，所以改用二分法查找～Func函数的作用是二分查找，修改tempsum和j的值～一开始接收输入的时候可以直接保存它的sum函数，即sum[i]表示1～i的所有数字的总和～

Mice and Rice is the name of a programming contest in which each programmer must write a piece of code to control the movements of a mouse in a given map. The goal of each mouse is to eat as much rice as possible in order to become a FatMouse.

First the playing order is randomly decided for NP programmers. Then every NG programmers are grouped in a match. The fattest mouse in a group wins and enters the next turn. All the losers in this turn are ranked the same. Every NG winners are then grouped in the next match until a final winner is determined.

For the sake of simplicity, assume that the weight of each mouse is fixed once the programmer submits his/her code. Given the weights of all the mice and the initial playing order, you are supposed to output the ranks for the programmers.

Input Specification:

Each input file contains one test case. For each case, the first line contains 2 positive integers: NP and NG (<= 1000), the number of programmers and the maximum number of mice in a group, respectively. If there are less than NG mice at the end of the player’s list, then all the mice left will be put into the last group. The second line contains NP distinct non-negative numbers Wi (i=0,…NP-1) where each Wi is the weight of the i-th mouse respectively. The third line gives the initial playing order which is a permutation of 0,…NP-1 (assume that the programmers are numbered from 0 to NP-1). All the numbers in a line are separated by a space.

Output Specification:

For each test case, print the final ranks in a line. The i-th number is the rank of the i-th programmer, and all the numbers must be separated by a space, with no extra space at the end of the line.

Sample Input:
11 3
25 18 0 46 37 3 19 22 57 56 10
6 0 8 7 10 5 9 1 4 2 3
Sample Output:
5 5 5 2 5 5 5 3 1 3 5

题目大意：np为老鼠的数量，ng为每组最多g个老鼠。先给出np个老鼠的重量，再给出老鼠的初始顺序（第i名的老鼠是第j号，j从0开始）。每ng个老鼠分为一组，对于每组老鼠，选出最重的那个，晋级下一轮比赛，然后依次再以np个老鼠一组分类，然后选出重量最大的。。。直到只剩下一只老鼠，排名为1.输出为老鼠的排名，这个排名是按照原输入老鼠的顺序输出的～
分析：设立结构体node表示老鼠，里面包括weight重量，index是按照排名后的顺序的老鼠的下标，index0是排名前老鼠的下标。rank是最终要输出的老鼠的排名。
先将所有的老鼠按照排名后的顺序依次放入队列中，对于队列中的每一个老鼠，按照分组后选择最大重量的比赛规则，将每次分组获得第一的老鼠放入队列尾部。此处有一点，如果当前剩下的老鼠可以分为group组，那么这一组里面没有晋级的老鼠排名就是group+1.此处解释一下：
因为对于共有group组的老鼠，每组晋级一个，也就是说最终这一轮能晋级的是group个老鼠，那么没有晋级的所有人就是group+1名，就像有4个人晋级下一轮，那么所有没晋级的这一轮就都是并列第5名。
group的计算方法是：如果当前轮次的人数正好可以被每组ng人的ng整除，那么就有人数/ng个组。如果不能被整除，就有剩下来的一些老鼠分为一组，就是人数/ng + 1组。（这是求得group的方法）
cnt用来控制当前的组内第几个人，如果cnt能够被ng整除了说明已经是下一组了，就cnt = 0；否则cnt不断++，同时将最重的老鼠体重赋值给maxn，最重的老鼠的node赋值给maxnode。
最后将结果结构体w排序，按照先前保存的index0的顺序排序，因为题目要求是必须按照题目所给的输入顺序输出的，排序后即可按序输出～