找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 2724|回复: 0
收起左侧

[米群网刷题小分队] [PAT-B] 1095 Cars on Campus

[复制链接]
发表于 5-3-2015 09:18 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
1095 Cars on Campus
给定车牌号和出入停车场记录,求每个时间点有多少车,以及在停车场里最长时间的车。
没啥好说的,同一个车……关键是in和out的处理,很多个in取最后一个,而很多个out取第一个。

  1. #include <algorithm>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <string>
  5. #include <vector>
  6. using namespace std;

  7. struct node {
  8. char s[10];
  9. int t;
  10. bool in;
  11. };


  12. const int M = 3600 * 24;
  13. int a[M];
  14. vector<node> v;
  15. char s[5];
  16. vector<string> answer;

  17. bool cmp(const node &a, const node &b) {
  18. int c = strcmp(a.s, b.s);
  19.         if (c < 0) {
  20.                 return true;
  21.         }
  22.         if (c > 0) {
  23.                 return false;
  24.         }
  25.         return a.t < b.t;
  26. }

  27. bool givein(int &i, int j) {
  28.         for (;(i < j) && (!v【i】.in); ++i)
  29.         ;
  30.         if (i >= j) {
  31.                 return false;
  32.         }
  33.         for (; (i < j) && (v【i】.in); ++i)
  34.         ;
  35.         --i;
  36.         return true;
  37. }       

  38. bool giveout(int &i, int j) {
  39.         for (; (i < j) && (v【i】.in); ++i)
  40.         ;
  41.         return i < j;
  42. }

  43. int main() {
  44. int n, q;
  45.         scanf("%d%d",&n,&q);
  46.         v.resize(n);
  47.         for (int i = 0; i < n; ++i) {
  48.                 int x, y, z;
  49.                 scanf("%s %d:%d:%d %s", v【i】.s, &x,&y,&z, s);
  50.                 v【i】.t = x * 3600 + y * 60 + z;
  51.                 v【i】.in = (s[0] == 'i');
  52.         }
  53.         sort(v.begin(), v.end(), cmp);
  54.         int best = -1;
  55.         for (int i = 0; i < n;) {
  56.                 int m;
  57.                 for (m = i; (m < n) && (strcmp(v【i】.s, v[m].s) == 0); ++m)
  58.                 ;
  59.                 string name = v【i】.s;
  60.                 int may = 0;
  61.                 for  (may = 0;;) {
  62.                         if (!givein(i, m)) {
  63.                                 break;
  64.                         }
  65.                         int j = i;
  66.                         if (!giveout(i, m)) {
  67.                                 break;
  68.                         }
  69.                         ++a[v[j].t];
  70.                         --a[v【i】.t];
  71.                         may += v【i】.t - v[j].t;
  72.                 }
  73.                 if (may > best) {
  74.                         best = may;
  75.                         answer.resize(1);
  76.                         answer[0] = name;
  77.                 }
  78.                 else if (may == best) {
  79.                         answer.push_back(name);
  80.                 }
  81.         }
  82.         for (int i = 1; i < M; ++i) {
  83.                 a【i】 += a[i - 1];
  84.         }
  85.         for (;q;--q) {
  86.                 int x, y, z;
  87.                 scanf("%d:%d:%d",&x,&y,&z);
  88.                 printf("%d\n",a[x * 3600 + y * 60 + z]);
  89.         }
  90.         for (int i = 0; i < answer.size(); ++i) {
  91.                 printf("%s ",answer【i】.c_str());
  92.         }
  93.         printf("%02d:%02d:%02d\n", best / 3600, best % 3600 / 60, best % 60);
  94. }

  95.                        
复制代码



本帖被以下淘专辑推荐:

我们始终相信IT会持续改造甚至创新传统行业,我们始终全面看好咱们的CS专业!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表