参考: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
