首页 > ACM题库 > HDU-杭电 > hdu 3897 Happy Trip待解决[解题报告]C++
2015
04-13

hdu 3897 Happy Trip待解决[解题报告]C++

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的边不是都没了吗?

  4. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。