torus711 のアレ

主に競技プログラミングの問題について書きます

Codeforces #201, Division 2, A : Difference Row

概要

N 項からなる a 数列が与えられる。
この数列を並び替え、次の値が最大になる辞書順最小の列を求めよ。
 \sum_{ i = 0 }^{ N - 2 }{ ( a_i - a_{ i + 1 } ) }

解法

初項と末項以外は正負で打ち消し合って消えるので、値を最大化するには最大値を初項、最小値を末項に配置しなければなりません。
それ以外については、辞書順最小にするために降順に並べればよいです。

コード

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )
#define ALL( c ) (c).begin(), (c).end()

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n;
	cin >> n;

	VI as( n );
	FOR( a, as )
	{
		cin >> a;
	}

	sort( ALL( as ), greater<int>() );
	reverse( as.begin() + 1, as.end() - 1 );

	REP( i, 0, n )
	{
		cout << as[i] << ( i + 1 == n ? '\n' : ' ' );
	}
	cout << flush;

	return 0;
}