3171.txt

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

Source

Problem Id:3171  User Id:fzk 
Memory:228K  Time:30MS
Language:C++  Result:Accepted

Source 

#include <stdio.h>
#include <algorithm>

using namespace std;
int t1[10000], t2[10000], f[10000], t[10000], fee[10000];
int id[10000];

bool cmp( int a, int b ) {
	return t2[a] < t2[b];
}

int main( ) {
	int i, n, m, e, tn, x, y, k, temp;
	
	scanf( "%d%d%d", &n, &m, &e );

	for( i=0; i<n; i++ ) {
		scanf( "%d%d%d", t1+i, t2+i, f+i );
		id[i] = i;
	}

	sort( id, id+n, cmp );

	tn = 1;
	fee[0] = 0;
	t[0] = m;

	for( i=0; i<n; i++ ) {
		x = t1[ id[i] ];
		y = t2[ id[i] ];
		k = lower_bound( t, t+tn, x ) - t;

		if( k < tn ) {
			temp = f[id[i]] + fee[k];
			while( tn && temp <= fee[tn-1] )
				tn--;
			fee[tn] = temp;
			t[tn] = y+1;
			tn++;
		}
	}

	if( t[tn-1] != e+1 )
		printf( "-1\n" );
	else
		printf( "%d\n", fee[tn-1] );

	return 0;
}