2015
04-13

# Happy Trip

What a tragedy… Liuctic’s iPhone is out of battery when he was in the subway. So he comes up with a problem to make a happier trip. There is a subway station. A piece of record, namely a pair of integers (t, N), would mean that N passengers entered the subway station at the t-th second. There are X trains, each of which has a maximum capacity of 2000 people. And for safety reasons, the time interval between any two trains’ arrival at the station would not be lesser than 60 seconds.
Give M pieces of record and X (the number of trains), your task is to calculate the minimum waiting time in sum for all passengers.

The integer in the first line indicates the number of test cases. For each test case, the first line will contain two integers M (0<M<=300) and X (0<X<=300). Then there comes M lines of records. The i-th records will contain two integers t(i) and N(i). And you can assume 0<=t(1)<t(2)<…<t(M).

The integer in the first line indicates the number of test cases. For each test case, the first line will contain two integers M (0<M<=300) and X (0<X<=300). Then there comes M lines of records. The i-th records will contain two integers t(i) and N(i). And you can assume 0<=t(1)<t(2)<…<t(M).

2
3 2
0 1998
15 2
40 5
3 2
0 1998
20 3
100 1999

190
INF
Hint
Case 1: The first train arrives at 0-th second. The second arrive at 60-th second. The waiting time in sum would be 2*(60-15) + 5*(60-40) = 190
Case 2: According to the restrictions, the two trains cannot manage to pick all the passengers away. So the output is "INF".


1. 第一句可以忽略不计了吧。从第二句开始分析，说明这个花色下的所有牌都会在其它里面出现，那么还剩下♠️和♦️。第三句，可以排除2和7，因为在两种花色里有。现在是第四句，因为♠️还剩下多个，只有是♦️B才能知道答案。

2. #include <cstdio>
#include <cstring>

const int MAXSIZE=256;
//char store[MAXSIZE];
char str1[MAXSIZE];
/*
void init(char *store) {
int i;
store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
for(i=’F';i<=’Z';++i) store =i-5;
}
*/
int main() {
//freopen("input.txt","r",stdin);
//init(store);
char *p;
while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
if(p=fgets(str1,MAXSIZE,stdin)) {
for(;*p;++p) {
//*p=store[*p]
if(*p<’A’ || *p>’Z') continue;
if(*p>’E') *p=*p-5;
else *p=*p+21;
}
printf("%s",str1);
}
fgets(str1,MAXSIZE,stdin);
}
return 0;
}

3. 在方法1里面：

//遍历所有的边，计算入度
for(int i=0; i<V; i++)
{
degree = 0;
for (j = adj .begin(); j != adj .end(); ++j)
{
degree[*j]++;
}
}

为什么每遍历一条链表，要首先将每个链表头的顶点的入度置为0呢？
比如顶点5，若在顶点1、2、3、4的链表中出现过顶点5，那么要增加顶点5的入度，但是在遍历顶点5的链表时，又将顶点5的入度置为0了，那之前的从顶点1234到顶点5的边不是都没了吗？