1019.cpp

我的URAL的1000 ~ 1050 的全部代码 包含WA 最后AC的程序 有2~3个比较难的是MAIGO的程序

//典型离散化
#include <iostream>
#include <algorithm>
using namespace std;

const int maxN = 20000;
int a[maxN + 1],line[maxN + 1];
char color[maxN + 1];//下标为奇数就是起点
int idx[maxN + 1],ori[maxN + 1];

int n,m,tot, ansbeg,ansend,anslen;

//bool cmp(const int &t1, const int &t2) { return a[t1] < a[t2]; }
inline bool cmp( const int *p1, const int *p2 ) { return a[(*p1)] < b[(*p2)] ; }
void readIn()
{
	int i,t;
	cin >> n;
	tot = n*2+2; //包括 1000000000
	a[1] = 0,a[2] = 1000000000, color[1] = 'w';
	for( i = 3; i <= tot ; i+=2 )
	 	{ cin >> a[i] >> a[i+1] >> color[i]; }

	for( i = 1; i <= tot; i++ ) idx[i] = i;
	sort( idx + 1, idx + 1 + tot, cmp );
	
	//离散化

	for( m = 0, i = 1; i <= tot; )
	{
		t = a[ idx[i] ], ++m; ori[m] = t;
		do  {a[ idx[i++] ] = m;} while ( i<=tot && a[ idx[i] ] == t);
	} 
	

}

void work()
{
	int i,j;
	memset( line, 0, sizeof(line) );
	
	for( i = 1; i<= tot; i+=2 )
	{
		for( j = a[i]; j < a[i+1]; j++ )
			if( color[i] == 'w' )
				line[j] = 1;
			else
				line[j] = 2;
	}
//	for( i = 1; i<= m-1; i++ )cout << line[i] <<' ' ; cout <<endl;
	int len = 0,beg,end;
	ansbeg = ansend = 0;
	for( i = 1; i <= m - 1 ; i++)
	{
		if(line[i] == 1)
		{
			if( line[i-1] != 1 )
				beg = ori[i];
			len += ori[i+1] - ori[i];
		}
		if(line[i] != 1 && line[i-1] ==1  )
		{
			if( anslen < len ) {anslen = len; ansbeg = beg; ansend = end = ori[i];}
			len = 0;
		}
	}
	if( anslen < len ) {anslen = len; ansbeg = beg; ansend = end = ori[i];}
}
int main()
{
 	freopen( "1019.in", "r", stdin );
	readIn();
	work();
	cout << ansbeg << ' ' << ansend << endl;
	return 0;
}