PAT 1017

题目 ： Queueing at Bank

分值 ： 25
难度 ： 中等细节题
思路 ： 细节题，string类型题，提醒我str2int 和int2str 需要弄个简单的方法了。
坑点 ： 坑点还行 
评语 ： 解决方案很容易想到，但是因为需要处理很多细节

具体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <iostream>
#include <string>
#include <algorithm>
using namespace std ;
typedef struct Node{
    string time ;
    int delay ;
}Nodes;
Nodes list[10000] ;
bool cmp( Node a , Node b )
{
    return a.time < b.time ;
}
double deal(string a ,string b )
{
    double h1 = (a[0]-'0')*10 + a[1]-'0' ;
    double m1 = (a[3]-'0')*10 + a[4]-'0' ;
    double s1 = (a[6]-'0')*10 + a[7]-'0' ;

    double h2 = (b[0]-'0')*10 + b[1]-'0' ;
    double m2 = (b[3]-'0')*10 + b[4]-'0' ;
    double s2 = (b[6]-'0')*10 + b[7]-'0' ;
    return (h1-h2)*60 + (m1-m2) + (s1-s2)/60;
}
string renew(string a  , int b)
{
    int h1 = (a[0]-'0')*10 + a[1]-'0' ;
    int m1 = (a[3]-'0')*10 + a[4]-'0' ;
    int s1 = (a[6]-'0')*10 + a[7]-'0' ;
    h1 += (m1+b)/60 ;
    m1 = (m1+b)%60 ;
    a[0] = '0'+ (h1/10) ;
    a[1] = '0'+ (h1%10) ;
    a[3] = '0'+(m1/10) ;
    a[4] = '0'+(m1%10) ;
    //cout <<"temp:" <<a <<endl ;
    return a ;
}
int main() {
    int N , K ;
    cin >> N>> K ;
    string queen[K] ;
    for(int i = 0 ;i< N ;i++)
    {
        cin >> list[i].time >> list[i].delay ;
        if(list[i].delay >= 60 )
            list[i].delay = 60 ;
    }
    for(int i = 0; i< K ;i++)
        queen[i] = "08:00:00" ;
    string end = "17:00:01" ;
    string small = "08:00:00" ;
    int index = 0 ;
    sort(list, list+N , cmp) ;
    //for(int i = 0 ;i < N ; i++)
        //cout << list[i].time <<" "<<list[i].delay <<endl ;
    double sum = 0 ;
    int count = 0 ;
    for(int i = 0 ; i< N ;i++)
    {
        if(list[i].time >= end )
            break ;
        count ++ ;
        //cout << index <<" "<<queen[index] << " "<<list[i].time <<endl ;
        if(queen[index] > list[i].time )
        {
            sum += deal(queen[index] , list[i].time) ;
            queen[index]  = renew(queen[index] , list[i].delay) ;
        }
        else
            queen[index]  = renew( list[i].time, list[i].delay) ;
        //cout << "test:" <<queen[index] <<endl ;
        small = queen[index] ;
            for(int j = 0 ; j< K ;j++)
            {
                if(queen[j] < small)
                {
                    small = queen[j ] ;
                    index = j ;
                }
            }
    }
    printf("%.1lf\n" , sum/count  );
    return 0 ;

}