PAT1095Cars on Campus
タイトルリンク:
http://www.nowcoder.com/pat/5/problem/4319
テーマ:
1.時間ごとにキャンパス内に何台の車があるかを統計する
2.キャンパス内にいる時間が一番長い車を見つける
肉のシミュレーション類の問題を比較して、無効なデータをどのように除去するかを知っていて、直接シミュレーションすればいいです.有効なペアリングとは、隣接する2つのinとout、すなわち連続する複数のinが最後の1つを有効とし、連続する複数のoutが最初の1つを有効とし、最後にinが一致していない場合は、対応する記録を放棄すべきである.灰さんはいつもこのブロガーのブログに感謝しています.
http://blog.csdn.net/sinat_29278271/article/details/48081177
自分が最初に書いたときに無効なデータをどう処理するかの見当は全くありませんでした.
コード:
http://www.nowcoder.com/pat/5/problem/4319
テーマ:
1.時間ごとにキャンパス内に何台の車があるかを統計する
2.キャンパス内にいる時間が一番長い車を見つける
肉のシミュレーション類の問題を比較して、無効なデータをどのように除去するかを知っていて、直接シミュレーションすればいいです.有効なペアリングとは、隣接する2つのinとout、すなわち連続する複数のinが最後の1つを有効とし、連続する複数のoutが最初の1つを有効とし、最後にinが一致していない場合は、対応する記録を放棄すべきである.灰さんはいつもこのブロガーのブログに感謝しています.
http://blog.csdn.net/sinat_29278271/article/details/48081177
自分が最初に書いたときに無効なデータをどう処理するかの見当は全くありませんでした.
map<string,int>
を用いて、車両名と滞留総時間とのマッピング関係を確立する.主に入力データの処理で、入力データを並べ替えて、先に車両名を並べて、もし車名が同じならば、時間の小さい列の前に並べます.比較すると、前のデータと後のデータは、車名が同じで、時間が異なり、前の状態がinと後の状態がoutで一致すると、後の時間で前の時間を減らし、滞在時間として、対応する車両名の総滞在時間に加算することができる.コード:
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string>
#include<algorithm>
#include<map>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
#define MAX 10005
const int MAXRANGE = 24*60*60;
string decToTime(int time)
{
char str[20];
sprintf(str,"%02d:%02d:%02d",time/(60*60),time/60%60,time%60);
return string(str);
}
int timeToDec(int h,int m,int s)
{
return (h * 60 + m) * 60 + s;
}// 10
class Car
{
public:
string ID;
int time;
bool out;
public:
bool isMatch(const Car &c)
{
return this->ID == c.ID&& this->time < c.time && this->out == false && c.out == true;
}
bool operator <(const Car &c) const// ,
{
if (this->ID != c.ID)
{
return this->ID < c.ID;
}
else if (this->time != c.time)
{
return this->time < c.time;
}
else
{
return !this->out;
}
}
//void Printf()
//{
// cout << ID <<" "<< time <<" "<< out << endl;
// cout << decToTime(time) << endl;
//}
};
Car cars[MAX];
int sumCnt[MAXRANGE];
int main()
{
int N, K;
cin >> N >> K;
for (int i = 0; i < N; i++)
{
int h, m, s;
cin >> cars[i].ID;
scanf("%d:%d:%d",&h,&m,&s);
cars[i].time = timeToDec(h,m,s);
string status;
cin >> status;
if (status == "out")
{
cars[i].out = true;
}
else
{
cars[i].out = false;
}
}
sort(cars,cars+N);
//
/*for (int i = 0; i < N; i++) { cars[i].Printf(); }*/
map<string, int> parkTime;
int maxParkTime = -1;
for (int i = 0; i < N-1; i++)
{
if (cars[i].isMatch(cars[i+1]))// i in, i+1 out,
{
parkTime[cars[i].ID] += cars[i + 1].time - cars[i].time;
if (maxParkTime < parkTime[cars[i].ID])
{
maxParkTime = parkTime[cars[i].ID];
}
sumCnt[cars[i].time]++;
sumCnt[cars[i+1].time]--;
}
}
for (int i = 1; i < MAXRANGE; i++)
{
sumCnt[i] += sumCnt[i-1];
}
for (int i = 0; i < K; i++)
{
int h, m, s;
scanf("%d:%d:%d",&h,&m,&s);
printf("%d
",sumCnt[timeToDec(h,m,s)]);
}
map<string, int>::iterator it;
for (it = parkTime.begin(); it != parkTime.end(); ++it)
{
if (it->second == maxParkTime)
{
cout << it->first << " ";
}
}
cout << decToTime(maxParkTime)<< endl;
system("pause");
return 0;
}