欲張り+データ構造-poj 3110 Jenny's First Exam

タイトルリンク:
http://poj.org/problem?id=3110
タイトル:
n科の試験があって、各科の試験は早めにdi日復習することができて、各科の試験は1日復習するだけで、しかも試験の前にdi日復習することができないことを要求します.試験の日は復習できません.n科の試験の日にあげて、最も遅く復習を始める日を求めます.
問題解決の考え方:
まず日付を0000年00月00日との日数差に変換し、試験時間によって遅いから早い順に並べ替え、後から前へ日数をスキャンし、現在の日が試験日であれば、その試験の科目を最も早い復習時間で後から前へ並べ替える優先キューに加え、現在の日に試験がなければキューから先頭(最も遅い復習を示す科目)を取り出し、現在の時間がそれより小さい場合は、完了できないことを示します.そうしないと、科目を復習します.
PS:
1、このような欲張りなやり方は巧みで、日数で処理します.
2、日数を日付に対応し、500年を1サイクルとして処理を加速させる.
詳細な説明コード:

#include<iostream>
#include<cmath>
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<string>
#include<string.h>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<ctime>
#include<bitset>
#define eps 1e-6
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define ll __int64
#define LL long long
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
#define M 1000000007
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;

#define Maxn 55000
int n;
int yd[2]={365,366};

int days[2][13]={0,31,28,31,30,31,30,31,31,30,31,30,31,
0,31,29,31,30,31,30,31,31,30,31,30,31};

struct DD
{
    int m,d,y;
};
struct Sub
{
    int cur,ea;
    char save[25];
    int dd;
}sub[Maxn];
bool cmp1(struct Sub a,struct Sub b) //           
{
    return a.cur>b.cur;
}

int isleap(int y) //     
{
    if((y%4==0&&y%100)||(y%400==0))
        return 1;
    return 0;
}

int dtoi(int y,int m,int d) //       0000 00 00    
{
    int res=0,yy=isleap(y);

    res+=y*365+(y-1)/4-(y-1)/100+(y-1)/400; //  0   
    for(int i=1;i<m;i++)
        res+=days[yy][i];
    return res+d-1; //  0      1   2 
}

//500    182621
DD itod(int cur)
{
    DD res;
    int i;

    res.y=cur/182621*500; //  0    500      

    for(cur=cur%182621;cur>=yd[isleap(res.y)];res.y++)
        cur-=yd[isleap(res.y)];
    for(i=1;cur>=days[isleap(res.y)][i];i++)
        cur-=days[isleap(res.y)][i];
    res.m=i;
    res.d=cur+1; //       0   1

    return res;
}
struct Inf  //                    
{
    int d;

    friend bool operator < (struct Inf a,struct Inf b)
    {
        return a.d<b.d;
    }
};
int main()
{
   //freopen("in.txt","r",stdin);
   //freopen("out.txt","w",stdout);
//   int sum=0;
//   for(int i=1;i<=500;i++)
//        sum+=yd[isleap(i)];
//   printf("%d
",sum);
    //DD dd=itod(0);
   // printf("%04d.%02d.%02d
",dd.y,dd.m,dd.d);
   while(~scanf("%d",&n))
   {
       for(int i=1;i<=n;i++)
       {
           scanf("%s",sub[i].save);
           int y,m,d;
           scanf("%2d.%2d.%4d",&d,&m,&y);
           sub[i].cur=dtoi(y,m,d);
           scanf("%d",&sub[i].dd);
           sub[i].ea=sub[i].cur-sub[i].dd;
       }
       sort(sub+1,sub+1+n,cmp1);
//       for(int i=1;i<=n;i++)
//           printf("%d ",sub[i].cur);
       priority_queue<struct Inf>myq;

       int la=sub[1].cur,s=1,e=n,le=n;
       bool ans=false;

       while(la) //        
       {
           bool ha=false;

           if(sub[s].cur==la) //     
           {
               struct Inf temp;
               temp.d=sub[s].ea;
               myq.push(temp); //          
               ha=true;
               s++;
           }

           if(!ha)  //      
           {
               if(!myq.empty()) //        
               {
                   struct Inf temp=myq.top();
                   myq.pop();
                   if(temp.d<=la) //       
                        le--;
                   else
                   {
                       ans=true; //         
                       printf("Impossible
");
                       break;
                   }
               }
           }
           if(!le) //         
           {
               DD tt=itod(la);
               ans=true;
               printf("%02d.%02d.%04d
",tt.d,tt.m,tt.y);
               break;
           }
           la--;
       }
       if(!ans) //       
            printf("Impossible
");
   }
   return 0;
}

/*
693963 693961 693960 Impossible
*/