贪心的思想首先要好好理解一下，这里给出了每一门考试开始的时间，和复习的最大提前时间（否则容易忘记），应该是枚举加贪心的思想
n的范围是50000，从大到小进行枚举，如果是考试的一天进堆，不是则找出最大的那个复习时间上限
比较难处理的是时间转化问题，我在这里是把它提前了31。1。1600作为一个起始时间，然后都做一个转换
第一个程序我是写了一个date的类，重载了各种操作，现在也觉得在这种比赛提里面如果没有必要还是少些类比较好，太复杂了，调试起来也不清晰
以下是ac代码：
#include<iostream>
#include<algorithm>
#define maxn 50005
int T[]={0,31,28,31,30,31,30,31,31,30,31,30,31};
using namespace std;
struct node
{
int test,bg,i;
friend bool operator<(node a,node b)
{
return a.test>b.test;
}
}in[maxn];
int n;
bool cmp2(int x,int y)
{
return in[x].bg<in[y].bg;
}
int leap(int y)
{
if((y%4==0&&y%100)||(y%400==0))return 1;
return 0;
}
int DtoI(int d,int m,int y)
{
int yy,mm,ret=0;
for(yy=1600;yy<y;yy++)
ret+=365+leap(yy);
for(mm=1;mm<m;mm++)
ret+=T[mm]+(int)(leap(y)&&mm==2);
ret+=d;
return ret;
}
void print(int x)
{
int yy,mm,dd;
for(yy=1600;x>=365+leap(yy);yy++)
{
x-=365+leap(yy);
if(!x)
{
printf("31.12.%04d\n",yy);
return;
}
}
for(mm=1;x>=T[mm]+(int)(leap(yy)&&mm==2);mm++)
{
x-=T[mm]+(int)(leap(yy)&&mm==2);
if(x==0)
{
printf("%02d.%02d.%04d\n",T[mm]+(int)(leap(yy)&&mm==2),mm,yy);
return;
}
}
printf("%02d.%02d.%04d\n",x,mm,yy);
}
int main()
{
//freopen("1","r",stdin);
scanf("%d",&n);
int i;
for(i=0;i<n;i++)
{
char str[12];
scanf("%s",str);
int d,m,y,t;
scanf("%d.%d.%d",&d,&m,&y);
scanf("%d",&t);
in[i].test=DtoI(d,m,y);
in[i].bg=in[i].test-t;
}
sort(in,in+n);
int maxd=in[0].test,index=-1;
int heap[maxn],heapsize=0;
bool yes=true;
int tmp=n;
for(;yes&&tmp;maxd--)
{
if(maxd==in[index+1].test)
{
heap[heapsize++]=index+1;
push_heap(heap,heap+heapsize,cmp2);
++index;
continue;
}
if(heapsize>0)
{
int top=heap[0];
pop_heap(heap,heap+heapsize,cmp2);
heapsize--;
if(in[top].bg>maxd)yes=false;
else tmp--;
}
}
if(!yes)
printf("Impossible\n");
else
{
print(maxd+1);
}
return 0;
}
posted on 2008-10-10 22:26
zoyi 阅读(248)
评论(0) 编辑 收藏 引用 所属分类:
acm 、
数据结构