PAT1016 × PAT1017

本次题解是综合1016和1017两道题来讲解，原因无他，因为这两道都是模拟题，综合字符串处理、排序等考点

　　接手一道模拟题，一定要快速且准确地了解模拟的过程，清晰题目涉及的关键信息。比如1016要计算电话费，你就要对先根据人名排序，后根据日期排序，再剔除无效信息，最后根据前后两条记录计算费用这样的整个流程要清晰明了。其次再是考究一些细枝末节的东西，数据要存成什么格式的（用int还是字符串）？根据需要或者计算方便，数据是否做转换或统一（把12：00：09这样的时间格式都转换成秒12*3600+0*60+9）？用什么数据结构存储(struct对象等等)？以及一些特殊边界的考虑。以上就是一个大体的做题流程思路。接下来详细讲一下这两道题。

1016

　　每一条记录我们都会使用一个node的结构体来存储，为了方便之后的运算，我们会顺便在node中开辟一个time变量存放从00:00:00到目前的时间总和(这和1017如出一辙)。读取完记录，我们要为记录排序，先按照人名的字典序排，名字相同则按照time变量大小从小到大排列。完成排列后就能够计算费用了，计算费用的技巧就是先算完整天数的费用+最后一个小时多出来的分钟数的费用，接下来就是加上最后一天的经历的小时的费用。

#include<cstdio>

#include<iostream>

#include<cstring>

#include<string>

#include<map>

#include<algorithm>

#include<vector>

using namespace std;

//最好不要c风格字符串和string类型混用，不然容易有问题

struct node{

    string name;

    int status,time,month,day,hour,minute;  //为了方便计算，先把时间统一换算为time

};

bool cmp(node a,node b){

    return a.name!=b.name?a.name<b.name:a.time<b.time;

}

int fine[]={};

//从00:00:00:00到目前总共多少钱

double BillFromZero(node n){

    double bill=fine[]*n.day+fine[n.hour]*n.minute;

    for(int i=;i<n.hour;++i)

        bill+=fine[i]*;

    return bill/100.0;

}

int main(){

    freopen("in.txt","r",stdin);

    for(int i=;i<;++i){

        scanf("%d",&fine[i]);

        fine[]+=fine[i]*;

    }

    int n;

    scanf("%d",&n);

    vector<node> vec_node(n);

    for(int i=;i<n;++i){

        cin>> vec_node[i].name;

        scanf("%d:%d:%d:%d",&vec_node[i].month,&vec_node[i].day,&vec_node[i].hour,&vec_node[i].minute);

        string temp;

        cin>>temp;

        vec_node[i].status=(temp=="on-line")?:;

        vec_node[i].time=vec_node[i].day**+vec_node[i].hour*+vec_node[i].minute;

    }

    sort(vec_node.begin(),vec_node.end(),cmp);

    map<string,vector<node>> node_map;

    for(int i=;i<n;i++){

        if(vec_node[i].name==vec_node[i-].name && vec_node[i-].status== &&vec_node[i].status==){

            node_map[vec_node[i-].name].push_back(vec_node[i-]);

            node_map[vec_node[i].name].push_back(vec_node[i]);

        }

    }

    //因为是each month一次，所以我们的月份都是一样的，不用考虑多个月份的情况

    for(auto i:node_map){  //i不是是迭代器，是map的元素

        auto vec=i.second;

        cout<<vec[].name<<" ";

        printf("%02d\n",vec[].month);

        double total=0.0;

        for(int j=;j<vec.size();j+=){

            double bill=BillFromZero(vec[j+])-BillFromZero(vec[j]);

            printf("%02d:%02d:%02d %02d:%02d:%02d %d $%.2f\n",vec[j].day,vec[j].hour,vec[j].minute,vec[j+].day,vec[j+].hour,vec[j+].minute,vec[j+].time-vec[j].time,bill);

            total+=bill;

        }

        printf("Total amount: $%.2f\n",total);

    }

    return ;

}

1017

　　1017在存储方面倒是和1016很像，特别是记录时间方面，都是把(xx:xx:xx)格式的时间直接换成一个int类型的总时间，事实证明这样十分利于运算操作，在对客户信息进行排序的方面也是类似。不同的是，这道题多了一个银行的窗口信息，但是这个关系不大，用一个数组来存储各个窗口目前的营业时间就行。

　　每个窗口拥有一个数值，从8.00(8*60*60)开始,如果还有客人（客人需在17.00.00之前到达）那么这个客人就被接待，选择所有窗口中时间值最低的那一个，该位客人的时间值如果大于窗口时间值，那么等待时间为0，同时窗口时间值变为客人时间值+处理时间，否则等待时间为窗口值-客人时间值，同时窗口时间值变为窗口时间值+处理时间 (处理时间超过60*60的按照60*60算)。

坑点

　　只要你是17.00.00之前到达的人，排到你的时候是17.00.00之后（*min>MAX_TIME ），银行也要为你服务，我原来一直一位17.00.00之后，银行就马上停止工作

#include<stdio.h>

#include<queue>

#include<algorithm>

#include<cstring>

using namespace std;

/*模拟（全部转化为秒来进行）

  每个窗口拥有一个数值，从8.00开始，这个时间的上限是17.00，如果没有超过17.00，则说明其还能接待客人

  如果还有客人（客人17.00.00之前到达）并且还有营业窗口的时间没有达到时间上限，那么这个客人就能够被接待，选择所有窗口中时间值最低的那一个，该位客人的时间值如果大于窗口时间值，那么等待

  时间为0，同时窗口时间值变为客人时间值+处理时间，否则等待时间为窗口值-客人时间值， 同时窗口时间值变为窗口时间值+处理时间 (处理时间超过60*60的按照60*60算)

*/

int windows[]={};

const int MAX_TIME=**;

struct customer{

    int arrive_time;

    int process_time;

}customers[];

bool cmp(customer a,customer b){

    return a.arrive_time < b.arrive_time;

}

int main(){

    freopen("in.txt","r",stdin);

    int n,k;

    scanf("%d %d",&n,&k);

    for(int i=;i<n;++i){

        int a,b,c,d;

        scanf("%d:%d:%d %d",&a,&b,&c,&d);

        customers[i].arrive_time=a**+b*+c;

        customers[i].process_time=d*;

    }

    sort(customers,customers+n,cmp);  //按照时间先来后到排序

    for(int i=;i<k;++i)

        windows[i]=**;  //初始化窗口，8点上班

    double total=;

    int i;

    for(i=;i<n;++i){

        auto min=min_element(windows,windows+k);

        if(customers[i].arrive_time>MAX_TIME)  //只要你是17.00.00之前到达的人，排到你的时候是17.00.00之后（*min>MAX_TIME ），银行也要为你服务

            break;

        if(customers[i].arrive_time>=*min){

            total+=;

            *min=customers[i].arrive_time+(customers[i].process_time>?:customers[i].process_time);

        }

        else{

            total+=*min-customers[i].arrive_time;

            *min+=(customers[i].process_time>?:customers[i].process_time);

        }

    }

    printf("%.1f",total//i);

    return ;

}

巴特西

PAT1016 × PAT1017

本次题解是综合1016和1017两道题来讲解，原因无他，因为这两道都是模拟题，综合字符串处理、排序等考点

1016

1017

坑点

最新文章

热门文章