美文网首页
PAT(Phone Bills)

PAT(Phone Bills)

作者: 小幸运Q | 来源:发表于2018-08-15 21:55 被阅读8次

    参考:https://blog.csdn.net/xyt8023y/article/details/46010349


    1. 题目有点奇葩:
    • 时间是打乱顺序给你的,而且不一定是有效数据(一个on对应一个off),需要从低到高排序,然后把无效数据过滤掉,如果过滤后没有on-off对的话就不打印。
    • 给了24个小时的cents/每分钟的开销。一百cents兑换一美元。

    为了解决on和off存储的问题,我选择使用正负号来区分on和off。


    分以下四种情况:
    i指向on,j指向off
    ++    i++  j++
    --    i=j+1 j+=2
    +-    i=j+1 j+=2
    -+    i++  j++
    

    我的流程:

    将输入写入vector后按照字母次序排序:

    // 打印的时候要按照字符大小排序(ascii码小的放前面)
    bool cmpstr(customer&left,customer&right){
      // 逐个字符比较,从小到大排序,防止前面一串出现重复
      int leftlen=strlen(left.name);
      int rightlen=strlen(right.name);
      int length=min(leftlen,rightlen);
      int i,j;
      for(i=0;i<length;i++){
        if(left.name[i]==right.name[i]){
    
        }
        else{
          return left.name[i]<right.name[i];
        }
      }
      return leftlen<rightlen;
    }
    

    数据清理:

    对每一个人的time进行排序:

      // 按照题目要求的字符串方式排序
      sort(v.begin(),v.end(),cmpstr);
      for(i=0;i<v.size();i++){
        // 对时间从小到大排序
        sort(v[i].time.begin(),v[i].time.end(),cmptime);
      }
    

    打印每个人的数据:

    边过滤边将合法的on-off插入vector中(记得取绝对值):

    void print(vector<customer>&v,int num){
      int i=0,j=1;
      float sum=0;
      // 计算总价
      vector<int>record;
      while(j<v[num].time.size()){
        if(v[num].time[i]>0&&v[num].time[j]<0){
          int start=v[num].time[i];
          int ending=v[num].time[j];
          record.push_back(start);
          record.push_back(ending);
        }
        if(v[num].time[j]>0){
          i++;
          j++;
        }
        else if(v[num].time[j]<0){
          i=j+1;
          j+=2;
        }
      }
      if(record.empty()){
        return;
      }
      printf("%s %02d\n",v[num].name,monthnow);
      for(i=0;i<record.size();i+=2){
        PrintTime(record[i]);
        PrintTime(abs(record[i+1]));
        int time=-(record[i]+record[i+1]);
        cout<<time<<" ";
        sum+=sumup(record[i],abs(record[i+1]));
      }
      printf("Total amount: $%.2f\n",sum);
    }
    

    根据开始结束时间计算收费

    float sumup(int start,int ending){
      int i,j;
      int start_hours=start/60;
      int start_minutes=start%60;
      int ending_hours=ending/60;
      int ending_minutes=ending%60;
      float cost=0;
      for(i=start_hours+1;i<ending_hours;i++){
        cost+=60*costs[i%24];
      }
      cost+=costs[ending_hours%24]*(ending_minutes);
      cost+=costs[start_hours%24]*(60-start_minutes);
      cost/=100;
      printf("$%.2f\n",cost);
      return cost;
    }
    

    以上模块有两个问题,一个在计算中不提前除以100.00的话有可能会溢出。一个是算法错了,在同一个小时内的call会出现计算错误,下面这个算法计算了start到0:0:0的开销如何减去ending到0:0:0的开销得出了正确的结论。

    double caculate(int t)
    {
        int i,j;
        double sum=0;
        for(i=0;i<t/60;i++)
        {
            sum+=costs[i%24]*60/100.0;
        }
        sum+=costs[i%24]*(t%60)/100.0;
        return sum;
    }
    double sumup(int start,int ending)
    {
        double cost=caculate(ending)-caculate(start);
        printf("$%.2lf\n",cost);
        return cost;
    }
    

    我的代码:

    #include<bits/stdc++.h>
    using namespace std;
    typedef struct customer{
      vector<int>time;
      // +on -off
      string name;
      int namehash;
    }customer;
    map<string,customer>m;
    
    int costs[24]={0};
    int monthnow=0;
    // 月份是固定的,单独存放
    vector<customer>v;
    
    // 查找hash值是否存在,不存在就返回-1
    int searchmap(char name[]){
      int i,j;
      if(m.count(name)==1){
        return 1;
      }
      return -1;
    }
    // 根据名字hash从小到大排列,方便二叉查找
    bool cmp(customer&left,customer&right){
      return left.namehash<right.namehash;
    }
    // 打印的时候要按照字符大小排序(ascii码小的放前面)
    bool cmpstr(customer&left,customer&right){
      // 逐个字符比较,从小到大排序,防止前面一串出现重复
      int leftlen=left.name.size();
      int rightlen=right.name.size();
      int length=min(leftlen,rightlen);
      int i,j;
      for(i=0;i<length;i++){
        if(left.name[i]==right.name[i]){
    
        }
        else{
          return left.name[i]<right.name[i];
        }
      }
      return leftlen<rightlen;
    }
    bool cmptime(int a,int b){
      return abs(a)<abs(b);
    }
    void PrintTime(int time){
      printf("%02d:%02d:%02d ",time/(60*24),(time%(60*24))/60,(time%(60*24))%60);
    }
    double caculate(int t)
    {
        int i,j;
        double sum=0;
        for(i=0;i<t/60;i++)
        {
            sum+=costs[i%24]*60/100.0;
        }
        sum+=costs[i%24]*(t%60)/100.0;
        return sum;
    }
    double sumup(int start,int ending)
    {
        double cost=caculate(ending)-caculate(start);
        printf("$%.2lf\n",cost);
        return cost;
    }
    void print(vector<customer>&v,int num){
      int i=0,j=1;
      double sum=0;
      // 计算总价
      vector<int>record;
      while(j<v[num].time.size()){
        if(v[num].time[i]>0&&v[num].time[j]<0){
          int start=v[num].time[i];
          int ending=v[num].time[j];
          record.push_back(start);
          record.push_back(ending);
        }
        if(v[num].time[j]>0){
          i++;
          j++;
        }
        else if(v[num].time[j]<0){
          i=j+1;
          j+=2;
        }
      }
      if(record.empty()){
        return;
      }
      printf("%s %02d\n",v[num].name.c_str(),monthnow);
      for(i=0;i<record.size();i+=2){
        PrintTime(record[i]);
        PrintTime(abs(record[i+1]));
        int time=-(record[i]+record[i+1]);
        cout<<time<<" ";
        sum+=sumup(record[i],abs(record[i+1]));
      }
      printf("Total amount: $%.2f\n",sum);
    }
    int main(){
      int i,j,input;
      for(i=0;i<24;i++){
        scanf("%d",&input);
        costs[i]=input;
      }
      scanf("%d",&input);
    
      char name[50],sign[20];
      int month,day,hour,minutes,namehash;
      for(j=0;j<input;j++){
        scanf("%s %d:%d:%d:%d %s",name,&month,&day,&hour,&minutes,sign);
        monthnow=month;
        // cout<<"))))))))"<<endl;
        if(!strcmp(sign,"off-line")){
          // 匹配offline成功则返回0
          int target=searchmap(name);
          if(target==-1){
            // 没找到
            customer c;
            c.name=name;
            //c.namehash=hashname(name);
            c.time.push_back((minutes+60*hour+24*60*day)*-1);
            m[name]=c;
            //v.push_back(c);
            // sort(v.begin(),v.end(),cmpstr);
          }
          else{
            m[name].time.push_back((minutes+60*hour+24*60*day)*-1);
            // v[target].time.push_back((minutes+60*hour+24*60*day)*-1);
          }
        }
        else{
          int target=searchmap(name);
          if(target==-1){
            // 没找到
            customer c;
            c.name=name;
            c.time.push_back(minutes+60*hour+24*60*day);
            m[name]=c;
          }
          else{
            m[name].time.push_back(minutes+60*hour+24*60*day);
          }
        }
      }
      for(map<string,customer>::iterator it=m.begin();it!=m.end();it++){
        v.push_back(it->second);
      }
      // 按照题目要求的字符串方式排序
      sort(v.begin(),v.end(),cmpstr);
      for(i=0;i<v.size();i++){
        // 对时间从小到大排序
        sort(v[i].time.begin(),v[i].time.end(),cmptime);
      }
      // 筛选每个customers的bills然后打印
      for(i=0;i<v.size();i++){
        print(v,i);
      }
    }
    

    测试数据:

    
    测试用例:
    72 53 94 95 71 82 31 1 97 36 8 94 44 22 3 51 58 72 27 57 7 39 55 80 38 
    CS07 07:11:04:05 off-line 
    CS05 07:15:19:37 on-line 
    CS09 07:26:10:05 on-line 
    CS00 07:29:08:20 off-line 
    CS00 07:27:16:05 on-line 
    CS06 07:25:13:50 off-line 
    CS07 07:17:08:03 on-line 
    CS04 07:25:02:50 on-line 
    CS02 07:05:09:47 on-line 
    CS03 07:23:18:20 on-line 
    CS05 07:30:05:51 on-line 
    CS06 07:08:11:57 off-line 
    CS05 07:13:18:12 on-line 
    CS07 07:21:07:52 off-line 
    CS08 07:14:12:34 off-line 
    CS04 07:21:18:49 off-line 
    CS00 07:31:11:35 on-line 
    CS09 07:03:10:58 on-line 
    CS08 07:17:01:46 off-line 
    CS06 07:02:02:30 off-line 
    CS07 07:16:08:51 on-line 
    CS02 07:29:17:32 off-line 
    CS03 07:14:19:43 on-line 
    CS05 07:12:06:43 off-line 
    CS09 07:25:04:45 off-line 
    CS04 07:23:15:19 on-line 
    CS08 07:03:10:42 on-line 
    CS03 07:01:12:02 off-line 
    CS07 07:30:07:23 off-line 
    CS03 07:28:14:33 off-line 
    CS00 07:08:18:33 off-line 
    CS08 07:13:13:44 off-line 
    CS02 07:30:13:47 on-line 
    CS06 07:14:21:54 on-line 
    CS00 07:09:21:00 on-line 
    CS02 07:24:12:24 off-line 
    CS09 07:24:19:24 off-line 
    CS03 07:16:02:33 on-line 
    对应输出应该为:
    CS00 07 27:16:05 29:08:20 2415 $1302.30 Total amount: $1302.30 
    CS02 07 05:09:47 24:12:24 27517 $14315.04 Total amount: $14315.04 
    CS03 07 23:18:20 28:14:33 6973 $3632.19 Total amount: $3632.19 
    CS06 07 14:21:54 25:13:50 15356 $8055.14 Total amount: $8055.14 
    CS07 07 17:08:03 21:07:52 5749 $2994.61 Total amount: $2994.61 
    CS08 07 03:10:42 13:13:44 14582 $7587.92 Total amount: $7587.92 
    CS09 07 03:10:58 24:19:24 30746 $15973.84 Total amount: $15973.84 
    你的输出为:
    CS00 07 27:16:05 29:08:20 2415 $1302.30 Total amount: $1302.30 
    CS02 07 05:09:47 24:12:24 27517 $14315.05
    

    相关文章

      网友评论

          本文标题:PAT(Phone Bills)

          本文链接:https://www.haomeiwen.com/subject/fcfnvftx.html