b549 數位相片檔名

/*
b549 nr102-5 北二區102年-5 數位相片檔名 
*/
#include <iostream>
#include <iomanip>
#include <set>
#include <map>
using namespace std;

map<int,int> used;                   // 已使用的 <時間 , 檔名>
map<int,int>::iterator mit;
map<int,int>::reverse_iterator rit;

bool can(int fn)                     // 傳入的檔名是否可用(符合雙遞增)
{
    if(used.size()<2) return true;    // 只有0或1個時，一定可以 
   int cnt=1;                        // 使用的 序列數，最多2個  
   mit=used.begin();                
   int fn1=mit->second, fn2=9999 ,fn3;   //第1個使用 一個序列 
   // 若有兩個序列，維持 fn1<fn2 
   for(++mit; mit!=used.end() ; ++mit)  // 從 第2個起與前一個比 
   {
    fn3=mit->second; // 第2個起的檔案編號
    if( fn3<fn1 )
    {
    if (cnt==2 )  return false;  //已兩個再加1個 x
    ++cnt; fn2=fn1; fn1=fn3;  //保持 fn1<fn2
    }
    else // fn3>fn1 可加入 fn1或fn2
{
if(fn3>fn2) fn2=fn3; //加至較大 的序列處，保留較小的序序編號 
else fn1=fn3;   // fn3<fn2無法加至 fn2，也保證 fn1=fn3<fn2 
}
   }
   if( cnt==2 && fn<fn1 ) return false;  //已兩個再加1個 x
   else return true;
}

int main( )

{
   int n , t ;
   int fn[1000];
   char c;
   for( n=0; n<1000; ++n) fn[n] = n;
    set <int>::iterator sit;  
   bool first=true;
   while( cin >> n )
   {
      set <int> nuse(fn,fn+1000);  //待用的檔號
      used.clear();      

       while( n-- )
       {
          cin >> c >> t;
           if( c == 'A' )
          {
             for( sit = nuse.begin(); sit != nuse.end(); ++sit )
             {
                int fn = *sit;   //檢查檔名編號 fn 是否可用
                if ( !can( fn ) ) continue;   // 不能用，下一個
                used[ t ] = fn;             // t 時，加可用檔名 fn
                nuse.erase( *sit );
                break;
             }
          }
          else
          {
             nuse.insert( used[t] );   // 未用的檔名，加一個
             used.erase( t );          // 已用的 map <t,fn> 刪一個
          }
       }
// 印出，若不是第一組，則印出 --
        if(first) first=false; else cout << "--\n";  
        rit = used.rbegin();  rit++;  //先至倒數第2個 
        cout << "PIC" << setfill ('0') << setw (3) << (rit->second) << endl;
        rit--;
        cout << "PIC" << setfill ('0') << setw (3) << (rit->second) << endl;
   }
   return 0 ;
}

/* 輸入範例 
10 A 0  A 1  A 2  A 3  D 2 A 4 D 1 A 5 D 4 A 6
14 A 0  A 1  A 2  A 3  D 2 A 4 D 1 A 5 D 4 A 6 D 3 A 7 D 0 A 8
14 A 0  A 1  A 2  A 3  D 2 A 4 D 1 A 5 D 5 A 6 A 7 D 0 A 8 A 9
14 A 0  A 1  A 2  A 3  D 2 A 4 D 1 A 5 D 5 A 6 A 7 A 8 D 4 A 9
15 A 0  A 1  A 2  A 3  D 2 A 4 D 1 A 5 D 5 A 6 A 7 A 8 D 4 A 9  A 10
17 A 0  A 1  A 2  A 3  D 2 A 4 D 1 A 5 D 5 A 6 A 7 A 8 D 4 A 9  A 10 D 6 A 11
19 A 0  A 1  A 2  A 3  D 2 A 4 D 1 A 5 D 5 A 6 A 7 A 8 D 4 A 9  A 10 D 6 A 11 D 11 A 12
9 A 0 A 1 A 2 A 3 D 2 A 4 D 1 D 0 A 5
9 A 0 A 1 A 2 A 3 D 2 A 4 D 1 A 5 A 6
10 A 0 A 1 A 2 A 3 A 4 D 2 A 5 A 6 D 3 A 7
輸出範例-----------------
PIC004
PIC001
--
PIC002
PIC003
--
PIC006
PIC007
--
PIC006
PIC001
--
PIC001
PIC002
--
PIC002
PIC004
--
PIC002
PIC004
--
PIC002
PIC004
--
PIC004
PIC005
--
PIC005
PIC003
*/