程式設計思維與實踐 Week10 模拟賽 B 團隊聚會（不支援C++11）

題目描述：

TA團隊每周都會有很多任務，有的可以單獨完成，有的則需要所有人聚到一起，開過會之後才能去做。但TA團隊的每個成員都有各自的事情，找到所有人都有空的時間段并不是一件容易的事情。

給出每位助教的各項事情的時間表，你的任務是找出所有可以用來開會的時間段。

input：

第一行一個數T（T≤100），表示資料組數。

對于每組資料，第一行一個數m（2 ≤ m ≤ 20），表示TA的數量。

對于每位TA，首先是一個數n（0≤ n≤100），表示該TA的任務數。接下來n行，表示各個任務的資訊，格式如下

​

​YYYY MM DD hh mm ss YYYY MM DD hh mm ss "some string here"​

​

每一行描述的資訊為：開始時間的年、月、日、時、分、秒；結束時間的年、月、日、時、分、秒，以及一些字元串，描述任務的資訊。

資料約定：

所有的資料資訊均為固定位數，位數不足的在在前面補前導0，資料之間由空格隔開。

描述資訊的字元串中間可能包含空格，且總長度不超過100。

所有的日期時間均在1800年1月1日00:00:00到2200年1月1日00:00:00之間。

為了簡化問題，我們假定所有的月份（甚至2月）均是30天的，資料保證不含有不合法的日期。

注意每件事務的結束時間點也即是該成員可以開始參與開會的時間點。

output：

對于每一組資料，首先輸出一行"Scenario #i:"，i即表明是第i組資料。

接下來對于所有可以用來開會的時間段，每一個時間段輸出一行。

需要滿足如下規則：

1. 在該時間段的任何時間點，都應該有至少兩人在場。
2. 在該時間段的任何時間點，至多有一位成員缺席。
3. 該時間段的時間長度至少應該1h。

所有的成員都樂意一天24h進行工作。

舉個例子，假如現在TA團隊有3位成員，TT、zjm、hrz。

那麼這樣的時間段是合法的：會議開始之初隻有TT和zjm，後來hrz加入了，hrz加入之後TT離開了，此後直到會議結束，hrz和zjm一直在場。

要求：

1. 輸出滿足條件的所有的時間段，盡管某一段可能有400年那麼長。
2. 時間點的格式為MM/DD/YYYY hh:mm:ss。
3. 時間段的輸出格式為"appointment possible from T0 to T1"，其中T0和T1均應滿足時間點的格式。
4. 嚴格按照格式進行比對，如果長度不夠則在前面補前導0。
5. 按時間的先後順序輸出各個時間段。
6. 如果沒有合适的時間段，輸出一行"no appointment possible"。
7. 每組資料末尾須列印額外的一行空行。

思路：

一個區間排程問題，但與普通的區間排程不同的是，有T組資料（這個條件可以忽略），有n個人，每個人又有mi件事情，每件事情對應了一個區間。這類似于n條時間軸，每個時間軸上有mi個區間的問題。

現在考慮可以開會的條件：1、至少有2個人。2、頂多缺席一人。3、開會時長大于等于1小時（這個可以暫時忽略，最後判斷時間差即可）。開會的條件有人數的限制，是以程式設計時需要考慮人數。為解決這個問題，将n條時間軸濃縮成一條，如果a在此時有事，則時間軸該時刻對應的值+1，如果b在此時也有事，時間軸再次+1。這就形成了在時間軸上若幹個區間，區間内所有的數+1的問題。

由于時間軸持續了上千年，過于龐大，周遊指派的方法不可能實作，是以考慮差分：在開始時刻+1，表示從現在開始，某個人忙了起來。結束時刻-1，表示從現在開始，這個人忙完了。同樣由于時間軸過于龐大，但是區間可能會較少，開數組用數組下标表示時刻的方法也不能實作，是以考慮map(同樣也是因為map可以自動排序，友善周遊)。

#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
long long d1=12,d2=30,d3=24,d4=60,d5=60;
long long year,mon,day,hour,mi,sec;
string c;
map<long long,int> ha;
struct node
{
  vector<pair<long long,long long> > t;
}a[110];
long long num(long long x)
{
  long long ans=0;
  sec=x%100;
  x/=100;
  mi=x%100;
  x/=100;
  hour=x%100;
  x/=100;
  day=x%100;
  x/=100;
  mon=x%100;
  x/=100;
  year=x;
  ans=ans+year*d1*d2*d3*d4*d5;
  ans=ans+(mon-1)*d2*d3*d4*d5;
  ans=ans+(day-1)*d3*d4*d5;
  ans=ans+hour* d4*d5;
  ans=ans+mi*d5;
  ans=ans+sec;
  return ans;
}
bool judge(long long a,long long b)//a>=b,判斷時間a-b是不是大于一個小時 
{
  if(num(a)-num(b)>=3600)
  return true;
  return false;
}
void output(long long x)//以01/01/1800 00:00:00格式輸出 
{
  sec=x%100;
  x/=100;
  mi=x%100;
  x/=100;
  hour=x%100;
  x/=100;
  day=x%100;
  x/=100;
  mon=x%100;
  x/=100;
  year=x;
  if(mon<10)
  cout<<0<<mon<<'/';
  else cout<<mon<<'/';
  if(day<10)
  cout<<0<<day<<'/';
  else cout<<day<<'/';
  cout<<year<<" ";
  if(hour<10)
  cout<<0<<hour<<':';
  else cout<<hour<<':';
  if(mi<10)
  cout<<0<<mi<<':';
  else cout<<mi<<':';
  if(sec<10)
  cout<<0<<sec;
  else cout<<sec;
}
int main()
{
  int T,n,m;
  cin>>T;
  for(int lll=1;lll<=T;lll++)
  {
    ha.clear();
    int tot=0;
    cin>>n;
    for(int i=1;i<=n;i++)//n個人 
    {
      cin>>m;//每個人m件事 
      if(m==0) continue;
      ++tot;
      for(int j=1;j<=m;j++)
      {
        pair<long long,long long> tmp;
        cin>>year>>mon>>day>>hour>>mi>>sec;
        long long l=(((((year*100+mon)*100+day)*100+hour)*100+mi)*100+sec);
        tmp.first=l;
        cin>>year>>mon>>day>>hour>>mi>>sec;
        l=(((((year*100+mon)*100+day)*100+hour)*100+mi)*100+sec);
        tmp.second=l;
        a[tot].t.push_back(tmp);
        ha[a[tot].t[j-1].first]++;
        ha[a[tot].t[j-1].second]--;
        getline(cin,c);
      }
    }
    
    cout<<"Scenario #"<<lll<<":"<<endl;
    long long from=18000101000000,to=22000101000000;
    bool flag=0;ha[to]=-1;
      long long busy=0,maxx=0,minn=from;
      for(map<long long,int>::iterator it=ha.begin();it!=ha.end();it++)
      {
          long long tmp1=it->first,tmp2=it->second;
          busy+=tmp2;
          if(busy<=1&&n-busy>=2)//在此刻可以開會了，記錄起始時間 minn
          {
              maxx=tmp1;
        minn=min(minn,tmp1);
          }
      else//會議結束，記錄結束時間maxx 
          {
              maxx=tmp1;
              if(judge(maxx,minn))//保證maxx一定比minn大 
              {
                  flag=true;
                  cout<<"appointment possible from ";
          output(minn);
          cout<<" to ";
          output(maxx);
          cout<<endl;
              }
              minn=to;
          }
    }
    maxx=to;
    if(judge(maxx,minn))
    {
        flag=true;
        cout<<"appointment possible from ";
      output(minn);
      cout<<" to ";
      output(maxx);
      cout<<endl;
    }
    if(!flag)
        cout<<"no appointment possible"<<endl;
    cout<<endl;
    
    /*for(int i=1;i<=tot;i++)
    {
      for(int j=0;j<a[i].t.size();j++)
      cout<<a[i].t[j].first<<" "<<a[i].t[j].second<<endl;
    }*/
    for(int i=1;i<=tot;i++)
    a[i].t.clear();
  }
  return 0;
}