3110.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Source

Problem Id:3110  User Id:fzk 
Memory:1932K  Time:2210MS
Language:C++  Result:Accepted

Source 

#include <stdio.h>
#include <queue>

using namespace std;

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

int getDays( int dd, int mm, int year ) {
	int res = (year-1700)*365 + (year-1700-1)/4 + days[mm-1] + dd;
	if( year > 1800 )
		res--;
	if( year > 1900 )
		res--;
	if( mm > 2 && year % 4 == 0 && ( year % 100 != 0 || year % 400 ==0 ) )
		res ++;
	return res;
}

void toDate( int &dd, int &mm, int &year, int s ) {
	int i, j, t;
	
	year = s/366 + 1700;

	while( getDays( 1, 1, year+1 ) <= s )
		year++;

	for( i=1; i<=12; i++ ) {
		t = days[i]-days[i-1];
		if( i == 2 && year%4 == 0 && ( year%100!=0 || year%400==0 ) )
			t++;
		for( j=1; j<=t; j++ )
			if( getDays( j, i, year ) == s ) {
				dd = j, mm = i;
				return;
			}
	}

	return;
}

struct Exam {
	char w[12];
	int dd, mm, yy;
	int s, t;
}exam[50000];

struct Cmp {
	bool operator()( Exam *a, Exam *b ) const {
		return a->t < b->t;
	}
};

priority_queue< Exam*, vector<Exam*>, Cmp > q;

bool cmp( const Exam &a, const Exam &b ) {
	return a.s>b.s;
}

int main( ) {
	int i, n, ans;
	bool key = true;
	for( i=1; i<=12; i++ )
		days[i] += days[i-1];

	scanf( "%d", &n );
	for( i=0; i<n; i++ ) {
		scanf( "%s%d.%d.%d%d", &exam[i].w, &exam[i].dd, &exam[i].mm, &exam[i].yy, &exam[i].t );
		exam[i].s = getDays( exam[i].dd, exam[i].mm, exam[i].yy );
		exam[i].t = exam[i].s-exam[i].t;
	}

	sort( exam, exam+n, cmp );
	
	ans = 10000000;
	for( i=0; i<=n && key; i++ ) {
		while( !q.empty() && ( i== n || ans > exam[i].s ) ) {
			if( ans < q.top()->t ) {
				key = false;
				break;
			}
			ans--;
			q.pop();
		}
		if( i < n ) {
			q.push( &exam[i] );
			ans = exam[i].s-1;
		}
	}

	if( !key )
		printf( "Impossible\n" );
	else {
		int a, b, c;
		toDate( a, b, c, ans+1 );
		printf( "%02d.%02d.%04d\n", a, b, c );
	}
	return 0;
}