PAT1016

题目链接：http://pat.zju.edu.cn/contests/pat-a-practise/1016

我的思想：将记录存入键值对map里，key为客户id，value为一个结构体数组，结构体为{时间，状态（off-line or on-line）},因为map容易是按key的升序排列，所以只要遍历map就好，先对结构体数组以time为key升序排序，保证时间的连贯性，然后找出匹配对，进行计算.. 计算麻烦点，在一个calcu的函数里，基本思想见代码注释。个人感觉麻烦了点，但是好理解，有更好的算法希望可以讨论讨论！

此题比较注意的地方在于：如果客户A没有合法匹配对，则什么信息都不输出。

  1 #include<iostream>
  2 #include<string>
  3 #include<map>
  4 #include<vector> 
  5 #include<iterator>
  6 #include<algorithm>
  7 #include<iomanip>
  8  using namespace std;
  9 
 10  struct Node
 11  {
 12      string time;
 13      string status;
 14      /*time记录时间，status记录off-line, on-line*/
 15  };
 16 
 17  /*计算时间及其费用*/
 18  int calcu(string start, string end, vector<double> &toll, double &cost)
 19  {
 20      int dd(0), hh(0), mm(0);
 21      int sh, sm;
 22      for(int i=0; i<3; ++i)
 23          if(i == 0)     
 24          { 
 25              sm = (start[9]-'0')*10 + (start[10]-'0');
 26              mm = (end[9]-start[9])*10 + (end[10]-start[10]);
 27              if(mm < 0 )
 28              {--hh; mm+=60;}
 29          }
 30          else if(i == 1)
 31          {
 32              sh = (start[6]-'0')*10 + (start[7]-'0');
 33              hh += (end[6]-start[6])*10 + (end[7]-start[7]);
 34              if(hh < 0)
 35                  {--dd; hh+=24;}        
 36          }
 37          else
 38              dd +=  (end[3]-start[3])*10 + (end[4]-start[4]);
 39     /*两天之间差的时间*/
 40     int minutes = dd*24*60+hh*60+mm;
 41     int val = minutes;
 42     int hour=sh;
 43     if(sm != 0)
 44     {
 45         sm = 60-sm;
 46         if(minutes > sm)
 47             cost = toll[sh]*sm;
 48         else
 49             cost = toll[sh]*minutes;
 50         /*注意此判断！*/
 51         minutes -=sm;
 52         ++hour;
 53     }
 54     /*将开始时间补全到整点并计算相应费用，后面的while循环用于计算每过60分钟，费用的总和*/
 55     while(minutes > 0)
 56     {
 57         if(minutes < 60)
 58         {
 59             cost += toll[hour%24]*minutes;
 60             minutes = -1;
 61         }
 62         else
 63         {
 64             minutes -= 60;
 65             cost += toll[hour%24]*60;
 66             ++hour;
 67         }
 68     }
 69     return val;
 70  }
 71 
 72  /*判断用户记录是否有合法匹配对，也是本题坑的地方*/
 73  bool legal(vector<Node> &temp)
 74  {
 75      for(int i=0; i<temp.size()-1; ++i)
 76         if(temp[i].status == "on-line" && temp[i+1].status == "off-line")
 77             return true;
 78     return false;         
 79  }
 80 
 81  bool comp(Node n1, Node n2)
 82  {
 83      if(n1.time < n2.time)
 84          return true;
 85      else
 86          return false;
 87  }
 88 
 89  int main()
 90  {
 91      int in;
 92      while(cin>>in)
 93      {
 94          vector<double> toll(24,0); toll[0]=in;
 95          for(int i=1; i<24; ++i)
 96              cin>>toll[i];
 97          int N; cin>>N;
 98         map<string, vector<Node>> record;
 99         for(int i=0; i<N; ++i)
100         {
101             string id, t, s;
102             cin>>id>>t>>s;
103             Node n={t, s};
104             record[id].push_back(n);
105             /*记录存入键值对里key为客户id，value为Node*/
106         }
107         map<string, vector<Node>>::iterator iter = record.begin();
108         string month(iter->second.begin()->time, 0, 2);
109         /*记录月份*/
110         for(; iter != record.end(); ++iter)
111         {
112             sort(iter->second.begin(), iter->second.end(), comp);
113             vector<Node> temp = iter->second;
114             if(legal(temp))/*是否有合法匹配对*/
115             {
116                 cout<<iter->first<<" "<<month<<endl;
117                 double sum(0);
118                 for(int i=0; i<temp.size()-1; ++i)
119                 {
120                     if(temp[i].status == "on-line" && temp[i+1].status == "off-line")
121                     {
122                         double cost(0);
123                         int minu = calcu(temp[i].time, temp[i+1].time, toll, cost);
124                         sum += cost;
125                         string s(temp[i].time, 3, 8);
126                         string e(temp[i+1].time, 3, 8);
127                         cout<<s<<" "<<e<<" "<<minu<<" "<<"$"<<fixed<<setprecision(2)<<cost/100<<endl;
128                     }
129                 }
130                 cout<<"Total amount: $"<<fixed<<setprecision(2)<<sum/100<<endl;
131             }
132         }
133      }
134      return 0;
135  }